ISSN:
1436-4646
Keywords:
Acyclic Subgraph Problem
;
Feedback Arc Set Problem
;
Facets of Polyhedra
;
Polynomial Time Algorithms
;
Weakly Acyclic Digraphs
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedral point of view and determine several classes of facets for the associated acyclic subgraph polytope. We also show that the separation problem for the facet defining dicycle inequalities can be solved in polynomial time. This implies that the acyclic subgraph problem can be solved in polynomial time for weakly acyclic digraphs. This generalizes a result of Lucchesi for planar digraphs.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582009
Permalink
