<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5725</id>
    <completedYear/>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>343</pageFirst>
    <pageLast>348</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>50</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Path Avoiding Forbidden Pairs Polytope</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Electronic Notes in Discrete Mathematics</parentTitle>
    <identifier type="doi">10.1016/j.endm.2015.07.057</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Marco Blanco</author>
    <submitter>Nam-Dung Hoang</submitter>
    <author>Ralf Borndörfer</author>
    <author>Michael Brückner</author>
    <author>Nam-Dung Hoang</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="brueckner">Brückner, Michael</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
