Finding disjoint paths with different path-costs: Complexity and algorithms

DOI10.1002/net.3230220705zbMath0761.90094OpenAlexW1997556033MaRDI QIDQ4022731

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

Publication date: 17 January 1993

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230220705

zbMATH Keywords

disjoint pathsstrongly NP-completepolynomial time heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (16)

Multicriteria movement synchronization scheduling problems and algorithms ⋮ The mixed evacuation problem ⋮ On finding Min-Min disjoint paths ⋮ Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms ⋮ Finding disjoint paths with related path costs ⋮ Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks ⋮ Finding paths with minimum shared edges ⋮ The disjoint shortest paths problem ⋮ Easy Cases of Deadlock Detection in Train Scheduling ⋮ The Mixed Evacuation Problem ⋮ On the complexity of the edge-disjoint min-min problem in planar digraphs ⋮ A method to optimize evacuation instructions ⋮ Unnamed Item ⋮ Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs ⋮ An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs ⋮ An effective algorithm for obtaining the whole set of minimal cost pairs of disjoint paths with dual arc costs

Cites Work

• 2-linked graphs
• Graph minors. XIII: The disjoint paths problem
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding disjoint paths with different path-costs: Complexity and algorithms