The complexity of finding two disjoint paths with min-max objective function
From MaRDI portal
Publication:584275
DOI10.1016/0166-218X(90)90024-7zbMath0693.05035OpenAlexW2019637647MaRDI QIDQ584275
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
Related Items (28)
Length-bounded disjoint paths in planar graphs ⋮ Multicriteria movement synchronization scheduling problems and algorithms ⋮ On finding Min-Min disjoint paths ⋮ Integral flow decomposition with minimum longest path length ⋮ Path Problems in Complex Networks ⋮ Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths ⋮ Finding disjoint paths with related path costs ⋮ Branch-and-cut methods for the network design problem with vulnerability constraints ⋮ On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks ⋮ Finding paths with minimum shared edges ⋮ The disjoint shortest paths problem ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty ⋮ On the complexity of the edge-disjoint min-min problem in planar digraphs ⋮ On shortest 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 ⋮ Scheduling problems in transportation networks of line topology ⋮ A note on approximating the min-max vertex disjoint paths on directed acyclic graphs ⋮ Connectivity and inference problems for temporal networks ⋮ Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs ⋮ The point-to-point delivery and connection problems: Complexity and algorithms ⋮ Balanced paths in acyclic networks: Tractable cases and related approaches ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms ⋮ Shortest Two Disjoint Paths in Polynomial Time ⋮ Computing the 2-blocks of directed graphs ⋮ Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints ⋮ Min-sum 2-paths problems
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
This page was built for publication: The complexity of finding two disjoint paths with min-max objective function
