Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Univ Vienna, Fac Comp Sci, Wahringer Str 29, A-1090 Vienna, Austria..
Univ Salzburg, Dept Comp Sci, Jakob Haringer Str 2, A-5020 Salzburg, Austria..
KTH, School of Computer Science and Communication (CSC).
2018 (English)In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 65, no 6, article id 36Article in journal (Refereed) Published
Abstract [en]

In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1 + is an element of)-approximation factor, the running time was recently improved to n(2)(+o(1)) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1 + is an element of)-approximation algorithm with m(1+)(o(1)) expected total update time, thus obtaining near-linear time. Moreover, we obtain m(1)(+)(o(1)) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn(0.9+o(1))-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, is an element of)-hop set introduced by Cohen [12] in the PRAM literature. An (h, is an element of)-hop set of a graph G = (V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1 + is an element of)-approximated by their h-hop distance (given by a path containing at most h edges) on G' = (V, E boolean OR F). Our algorithm can maintain an (n(o(1)), is an element of)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Madry [27]. These two new tools might be of independent interest.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2018. Vol. 65, no 6, article id 36
Keywords [en]
Approximate shortest paths, hop sets
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-240781DOI: 10.1145/3218657ISI: 000452840200002Scopus ID: 2-s2.0-85057196421OAI: oai:DiVA.org:kth-240781DiVA, id: diva2:1275928
Note

QC 20190107

Available from: 2019-01-07 Created: 2019-01-07 Last updated: 2019-01-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Nanongkai, Danupon
By organisation
School of Computer Science and Communication (CSC)
In the same journal
Journal of the ACM
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 2 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf