EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths

Sunny Atalig, Alexander Hickerson, Arrdya Srivastav, Tingting Zheng, Marek Chrobak

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →