The complexity of finding two disjoint paths with min-max objective function
From MaRDI portal
Publication:584275
DOI10.1016/0166-218X(90)90024-7zbMath0693.05035MaRDI QIDQ584275
S. Thomas McCormick, David Simchi-Levi, Chung-Lun Li
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
Balanced paths in acyclic networks: Tractable cases and related approaches, Connectivity and inference problems for temporal networks, Finding disjoint paths with related path costs, The point-to-point delivery and connection problems: Complexity and algorithms, The disjoint shortest paths problem, Length-bounded disjoint paths in planar graphs
Cites Work
- Unnamed Item
- The directed subgraph homeomorphism problem
- Some simplified NP-complete graph problems
- Parallel concepts in graph theory
- A quick method for finding shortest pairs of disjoint paths
- Disjoint paths in a network
- On the Complexity of Timetable and Multicommodity Flow Problems
- Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- The complexity of finding maximum disjoint paths with length constraints