Efficient approximation algorithms for computing k disjoint constrained shortest paths

DOI10.1007/S10878-015-9934-2MaRDI QIDQ328701zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Improved LP-rounding approximations for the \(k\)-disjoint restricted shortest paths problem
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• Improved approximation algorithms for computing k disjoint paths subject to two constraints
• The Directed Disjoint Shortest Paths Problem
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• A quick method for finding shortest pairs of disjoint paths
• A simple efficient approximation scheme for the restricted shortest path problem
• Combinatorial optimization. Theory and algorithms.
• Disjoint paths in a network
• Finding disjoint paths with related path costs
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• Network flows. Theory, algorithms, and applications.
• On finding Min-Min disjoint paths
• 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

Cited in

(7)

• On the complexity of algorithms for detecting \(k\)-length negative cost cycles
• A heuristic algorithm for multi-constrained shortest link-disjoint paths
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• Improved LP-rounding approximations for the \(k\)-disjoint restricted shortest paths problem
• A novel approach to subgraph selection with multiple weights on arcs
• An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem
• Improved approximation algorithms for computing \(k\) disjoint paths subject to two constraints

This page was built for publication: Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths

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