Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths

DOI10.1007/s10878-015-9934-2zbMath1354.90153OpenAlexW2472937526MaRDI QIDQ328701

Longkun Guo

Publication date: 20 October 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9934-2

zbMATH Keywords

\(k\)-disjoint constrained shortest pathbifactor approximation algorithmcycle cancellationflow theoryLP rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

A novel approach to subgraph selection with multiple weights on arcs, On the complexity of algorithms for detecting \(k\)-length negative cost cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of the edge-disjoint min-min problem in planar digraphs
• The complexity of finding two disjoint paths with min-max objective function
• Finding disjoint paths with related path costs
• On finding Min-Min disjoint paths
• A quick method for finding shortest pairs of disjoint paths
• Disjoint paths in a network
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• Combinatorial optimization. Theory and algorithms.
• A simple efficient approximation scheme for the restricted shortest path problem