Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 33 (1985), S. 28-42 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...