Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 6 von 13
Zurück zur Trefferliste

On the Path Avoiding Forbidden Pairs Polytope

  • Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair.
Metadaten
Verfasserangaben:Marco Blanco, Ralf BorndörferORCiD, Michael Brückner, Nam-Dung Hoang, Thomas Schlechte
Dokumentart:Artikel
Titel des übergeordneten Werkes (Englisch):Electronic Notes in Discrete Mathematics
Band:50
Erste Seite:343
Letzte Seite:348
Jahr der Erstveröffentlichung:2015
DOI:https://doi.org/10.1016/j.endm.2015.07.057
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.