On the difficulty of some shortest path problems
DOI10.1145/1186810.1186815zbMATH Open1321.68283OpenAlexW2075543862MaRDI QIDQ2944541FDOQ2944541
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
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
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)
Cited In (17)
- Shortest Paths with Bundles and Non-additive Weights Is Hard
- Shortest paths avoiding forbidden subpaths
- Title not available (Why is that?)
- Computing strictly-second shortest paths
- 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
- Tight hardness for shortest cycles and paths in sparse graphs
- Title not available (Why is that?)
- Optimal shortest path set problem in undirected graphs
- Faster replacement paths
- Near optimal algorithms for the single source replacement paths problem
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)
