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

lower boundshortest pathreplacement path\(k\) shortest simple paths

Mathematics Subject Classification ID

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

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

(17)

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

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)