On the complexity of the planar directed edge-disjoint paths problem

DOI10.1007/s10107-005-0653-9zbMath1079.05046OpenAlexW2055564944MaRDI QIDQ2583126

Dirk Müller

Publication date: 13 January 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0653-9

zbMATH Keywords

NP-completenessPlanar graphsIntegral two-commodity-flows

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Multiflow Feasibility: An Annotated Tableau ⋮ The hardness of routing two pairs on one face

Cites Work

• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Integer plane multiflows with a mixed number of demands
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the complexity of the disjoint paths problem
• Planar Formulae and Their Uses
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Finding k Disjoint Paths in a Directed Planar Graph
• Combinatorial optimization. Theory and algorithms

This page was built for publication: On the complexity of the planar directed edge-disjoint paths problem