EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Michal Dory, Sebastian Forster, Yasamin Nazari, Tijn de Vos

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

All-pairs shortest pathsApproximate shortest pathsDecremental graph algorithmDistance oracle

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