The complexity of finding two disjoint paths with min-max objective function
From MaRDI portal
The paper considers the problem of finding two disjoint paths from a given node s to another node t in a network such that the length of the longer path is minimized. The paths may be vertex-disjoint or arc- disjoint and the network may be directed or undirected. It is shown that all four versions as well as some related problems are strongly NP- complete. The paper also gives a pseudo-polynomial-time algorithm for the acyclic directed case.
Recommendations
Cites work
- 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
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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
(36)- The point-to-point delivery and connection problems: Complexity and algorithms
- The disjoint shortest paths problem
- Length-bounded disjoint paths in planar graphs
- Branch-and-cut methods for the network design problem with vulnerability constraints
- 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
- Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty
- Improved approximation algorithms for computing k disjoint paths subject to two constraints
- On finding Min-Min disjoint paths
- On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks
- Scheduling problems in transportation networks of line topology
- Min-sum 2-paths problems
- Path Problems in Complex Networks
- Hardness of finding two edge-disjoint Min-Min paths in digraphs
- Multicriteria movement synchronization scheduling problems and algorithms
- Integral flow decomposition with minimum longest path length
- Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Finding paths with minimum shared edges
- Finding disjoint paths with different path-costs: Complexity and algorithms
- On the complexity of the edge-disjoint min-min problem in planar digraphs
- On shortest disjoint paths in planar graphs
- The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Balanced paths in acyclic networks: Tractable cases and related approaches
- Shortest two disjoint paths in polynomial time
- Computing the 2-blocks of directed graphs
- Connectivity and inference problems for temporal networks
- Algorithms and Computation
- AI 2005: Advances in Artificial Intelligence
- A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem
- Computing disjoint paths with length constraints
- A note on approximating the min-max vertex disjoint paths on directed acyclic graphs
- Snapshot disjointness in temporal graphs
- Computational complexity of the recoverable robust shortest path problem with discrete recourse
- On the approximability of train routing and the min-max disjoint paths problem
- Finding disjoint paths with related path costs
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)
