A branch and bound algorithm for the acyclic subgraph problem |
| |
Authors: | R. Kaas |
| |
Affiliation: | Instituut voor Actuariaat en Econometrie, Universiteit van Amsterdam, 1011 NH Amsterdam, Netherlands |
| |
Abstract: | A branch and bound algorithm for the acyclic subgraph problem (feedback are set problem) is described. The branching scheme lexicographically enumerates all permutations, skipping initial segments known by some easy tests not to have any optimal completion. A lower bound for the number of feedback arcs is given by the size of any collection of disjoint cycles. We propose a heuristic algorithm to find a large collection. The size of the problems our branch and bound algorithm can solve varies from 25 to 34 nodes, depending on the nature of the problem. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|