Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
The Maximum Flow Problem with Conflict and Forcing Conditions
verfasst von : Ulrich Pferschy, Joachim Schauer
Erschienen in: Network Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A
negative disjunctive constraint
states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this,
positive disjunctive constraints
force that for certain pairs of arcs at least one arc has to carry flow in a feasible solution.
Negative (positive) disjunctive constraints can be represented by a
conflict (forcing) graph
whose vertices correspond to the arcs of the underlying graph, and whose edges encode the constraints.
We show that the maximum flow problem is strongly
$\mathcal{NP}$
-hard, even if the conflict graph contains only isolated edges and the network consists only of disjoint paths. For forcing graphs the problem can be solved efficiently if fractional flow values are allowed. If flow values are required to be integral we provide the sharp line between polynomially solvable and strongly
$\mathcal{NP}$
-hard instances.