A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

Research output: Contribution to journalArticlepeer-review

Original languageEnglish
Pages (from-to)98-137
Number of pages40
JournalSIAM Journal on Computing
Volume50
Issue number3
DOIs
Publication statusPublished - 2021

Bibliographical note

Funding Information:
The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement No. 340506 and ERC grant agreement No. 317532. Supported by the Swedish Research Council (Reg. No. 2015-04659, ``Algorithms and Complexity for Dynamic Graph Problems"").

Funding Information:
\ast Received by the editors October 7, 2016; accepted for publication (in revised form) February 26, 2018; published electronically October 21, 2019. A preliminary version of this paper appeared in Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016 [40]. https://doi.org/10.1137/16M1097808 Funding: The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement No. 340506 and ERC grant agreement No. 317532. Supported by the Swedish Research Council (Reg. No. 2015-04659, ``Algorithms and Complexity for Dynamic Graph Problems""). \dagger Faculty of Computer Science, University of Vienna, 1090 Vienna, Austria (mhenzinger@ gmail.com). \ddagger Department of Computer Sciences, University of Salzburg, 5020 Salzburg, Austria (sk@cosy. sbg.ac.at). \S Department of Theoretical Computer Science, KTH Royal Institute of Technology, 10044 Stockholm, Sweden (danupon@gmail.com).

Publisher Copyright:
© 2019 Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai.

Fields of Science and Technology Classification 2012

  • 102 Computer Sciences

Keywords

  • Approximation
  • Distributed algorithms
  • Shortest paths

Cite this