The complexity of finding two disjoint paths with min-max objective function

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)

zbMATH Keywords

paths; NP-complete; arc-disjoint; vertex-disjoint

Mathematics Subject Classification ID

05C38: Paths and cycles

05C20: Directed graphs (digraphs), tournaments

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, Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms

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