Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
ACM Transactions on Algorithms · 31.07.2026 · 22 (3) · 1-21
DOI: 10.1145/3816151 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 06.07.2026. Verfasst von Sunny Atalig und 4 weiteren Autor:innen. Die Arbeit nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.
Abstract (Originalsprache)
We consider the classical single-source shortest path problem in directed weighted graphs. Eppstein proved recently an \(\Omega(n^{3})\) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this \(\Omega(n^{3})\) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm.
Förderung
- National Science Foundation
Zitieren
APA
Atalig, S., Hickerson, A., Srivastav, A., Zheng, T., & Chrobak, M. (2026). Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths. ACM Transactions on Algorithms, 22(3), 1-21. https://doi.org/10.1145/3816151
Vancouver
Atalig S, Hickerson A, Srivastav A, Zheng T, Chrobak M. Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths. ACM Transactions on Algorithms. 2026;22(3):1-21. doi:10.1145/3816151
BibTeX
@article{Atalig2026,
author = {Atalig, Sunny and Hickerson, Alexander and Srivastav, Arrdya and Zheng, Tingting and Chrobak, Marek},
title = {Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths},
journal = {ACM Transactions on Algorithms},
year = {2026},
volume = {22},
number = {3},
pages = {1--21},
doi = {10.1145/3816151}
}
EUVIMED