Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929586790465536 |
|---|---|
| author | Atalig, Sunny Hickerson, Alexander Srivastav, Arrdya Zheng, Tingting Chrobak, Marek |
| author_facet | Atalig, Sunny Hickerson, Alexander Srivastav, Arrdya Zheng, Tingting Chrobak, Marek |
| contents | We consider the classical single-source shortest path problem in directed weighted graphs. D.~Eppstein proved recently an $Ω(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 $Ω(n^3)$ lower bound to \emph{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06546 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths Atalig, Sunny Hickerson, Alexander Srivastav, Arrdya Zheng, Tingting Chrobak, Marek Data Structures and Algorithms We consider the classical single-source shortest path problem in directed weighted graphs. D.~Eppstein proved recently an $Ω(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 $Ω(n^3)$ lower bound to \emph{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. |
| title | Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.06546 |