New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
Algorithmica · 2026-12 · 88 (6)
DOI: 10.1007/s00453-026-01407-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 28.09.2026. Verfasst von Michal Dory und 3 weiteren Autor:innen. Beteiligte Einrichtung: University of Haifa, Haifa, Israel. Die Arbeit nennt 90 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Israel Science Foundation, Horizon 2020 Framework Programme, Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung.
Abstract (Originalsprache)
We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with m edges and n nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is $$(2+ \epsilon )$$ ( 2 + ϵ ) -APSP with total update time $$\tilde{O}(m^{1/2}n^{3/2})$$ O ~ ( m 1 / 2 n 3 / 2 ) (when $$m= n^{1+c}$$ m = n 1 + c for any constant $$0
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- University of Haifa, Haifa, Israel.
- Department of Computer Science, University of Salzburg, Salzburg, Austria.
- VU Amsterdam, Amsterdam, Netherlands.
- TU Graz, Graz, Austria.
Förderung
- Israel Science Foundation
- Horizon 2020 Framework Programme
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- Austrian Science Fund
Zitieren
APA
Dory, M., Forster, S., Nazari, Y., & de Vos, T. (2026). New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths. Algorithmica, 88(6). https://doi.org/10.1007/s00453-026-01407-2
Vancouver
Dory M, Forster S, Nazari Y, de Vos T. New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths. Algorithmica. 2026;88(6). doi:10.1007/s00453-026-01407-2
BibTeX
@article{Dory2026,
author = {Dory, Michal and Forster, Sebastian and Nazari, Yasamin and de Vos, Tijn},
title = {New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths},
journal = {Algorithmica},
year = {2026},
volume = {88},
number = {6},
doi = {10.1007/s00453-026-01407-2}
}
EUVIMED