An optimal absolute approximation algorithm for computing k restricted shortest paths

DOI10.1007/978-981-96-1090-7_2MaRDI QIDQ6970749zbMATH OpenFDO

Authors Yue Sun, Donglei Du, Longkun Guo, Dachuan Xu

Publication date 17 June 2025

Full work available at URL https://doi.org/10.1007/978-981-96-1090-7_2

zbMATH Keywords

absolute approximationdisjoint pathLP roundingquality of servicerestricted shortest path

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A dual algorithm for the constrained shortest path problem
• Approximation Schemes for the Restricted Shortest Path Problem
• Disjoint paths in a network
• Efficient approximation algorithms for computing \(k\) disjoint constrained shortest paths
• Graph theory
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• Shortest disjoint paths on a grid
• The NP-Completeness of Edge-Coloring

This page was built for publication: An optimal absolute approximation algorithm for computing \(k\) restricted shortest paths

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