On the difficulty of some shortest path problems

DOI10.1145/1186810.1186815MaRDI QIDQ2944541zbMATH OpenOpenAlexFDO

Authors Amit M. Bhosle, John Hershberger, Subhash Suri

Publication date 2 September 2015

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1186810.1186815

zbMATH Keywords

\(k\) shortest simple pathslower boundreplacement pathshortest path

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 1962826
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• Automata, Languages and Programming
• Faster replacement paths
• A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs

Cited in

(20)

• Shortest-path-preserving rounding
• Optimal shortest path set problem in undirected graphs
• Improved algorithms for replacement paths problems in restricted graphs
• Computing strictly-second shortest paths
• scientific article; zbMATH DE number 6707504 (Why is no real title available?)
• On the complexity of finding paths in a two-dimensional domain I: Shortest paths
• On the power of tree-depth for fully polynomial FPT algorithms
• scientific article; zbMATH DE number 1962826 (Why is no real title available?)
• Tight hardness for shortest cycles and paths in sparse graphs
• Shortest Paths with Bundles and Non-additive Weights Is Hard
• Replacement paths via row minima of concise matrices
• Near optimal algorithms for the single source replacement paths problem
• Shortest paths avoiding forbidden subpaths
• On Some Special Network Flow Problems: The Shortest Path Tour Problems
• Faster replacement paths
• Single source distance oracle for planar digraphs avoiding a failed node or link
• Stochastic Algorithms: Foundations and Applications
• A lower bound for the shortest path problem
• Near optimal algorithm for the directed single source replacement paths problem
• A nearly linear time construction of approximate single-source distance sensitivity oracles

This page was built for publication: On the difficulty of some shortest path problems

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