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

DOI10.1016/0166-218X(90)90024-7MaRDI QIDQ584275zbMATH OpenOpenAlexFDO

Authors S. Thomas McCormick, David Simchi-Levi, Chung-Lun Li

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(90)90024-7

zbMATH Keywords

pathsNP-completearc-disjointvertex-disjoint

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Recommendations

• Finding disjoint paths with different path-costs: Complexity and algorithms
• On finding Min-Min disjoint paths
• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• The disjoint shortest paths problem
• On the complexity of the edge-disjoint min-min problem in planar digraphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A quick method for finding shortest pairs of disjoint paths
• Disjoint paths in a network
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• On the Complexity of Timetable and Multicommodity Flow Problems
• Parallel concepts in graph theory
• Some simplified NP-complete graph problems
• The complexity of finding maximum disjoint paths with length constraints
• The directed subgraph homeomorphism problem

Cited in

(35)

• Min-sum 2-paths problems
• The point-to-point delivery and connection problems: Complexity and algorithms
• The disjoint shortest paths problem
• 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
• Computing the 2-blocks of directed graphs
• The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
• Computational complexity of the recoverable robust shortest path problem with discrete recourse
• Multicriteria movement synchronization scheduling problems and algorithms
• On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks
• Snapshot disjointness in temporal graphs
• Balanced paths in acyclic networks: Tractable cases and related approaches
• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• Connectivity and inference problems for temporal networks
• Integral flow decomposition with minimum longest path length
• Branch-and-cut methods for the network design problem with vulnerability constraints
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Length-bounded disjoint paths in planar graphs
• A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem
• AI 2005: Advances in Artificial Intelligence
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
• On the complexity of the edge-disjoint min-min problem in planar digraphs
• Finding disjoint paths with related path costs
• On shortest disjoint paths in planar graphs
• Scheduling problems in transportation networks of line topology
• Finding paths with minimum shared edges
• Improved approximation algorithms for computing k disjoint paths subject to two constraints
• Finding disjoint paths with different path-costs: Complexity and algorithms
• Shortest two disjoint paths in polynomial time
• Path Problems in Complex Networks
• Algorithms and Computation
• A note on approximating the min-max vertex disjoint paths on directed acyclic graphs
• Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty
• Computing disjoint paths with length constraints
• On finding Min-Min disjoint paths

This page was built for publication: The complexity of finding two disjoint paths with min-max objective function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q584275)