New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yasamin Nazari, Tijn de Vos · 2026
Read New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths by Michal Dory, Sebastian Forster, Yasamin Nazari, Tijn de Vos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/PMC13619683.txt.
Description
Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos work on a hard problem in graph algorithms: keeping shortest-path estimates current while edges are deleted one by one. Exact answers for every pair of points are too slow for huge networks, so researchers accept near answers that run faster. The question is how much accuracy must be traded for speed.
The team presents four new algorithms, two for weighted graphs and two for unweighted ones, each with its own balance of stretch and total update time. Their bounds improve on earlier tradeoffs in the ranges they target. Readers get formulas stating how the running time grows with the number of nodes and edges, together with proofs that the stated accuracy holds. The work is theoretical, aimed at algorithm designers who maintain routes on changing networks.
Catalog record
| CREATOR | Michal Dory, Sebastian Forster, Yasamin Nazari, Tijn de Vos |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 579 KB |
| LICENSE | https://creativecommons.org/licenses/by/4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |