On the difficulty of some shortest path problems

DOI10.1145/1186810.1186815zbMath1321.68283OpenAlexW2075543862MaRDI QIDQ2944541

Amit M. Bhosle, J. E. 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

shortest pathlower boundreplacement path\(k\) shortest simple paths

Mathematics Subject Classification ID

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

Related Items (3)

Shortest paths avoiding forbidden subpaths ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ Unnamed Item

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