---
res:
bibo_abstract:
- 'The decremental single-source shortest paths (SSSP) problem concerns maintaining
the distances between a given source node s to every node in an n-node m-edge
graph G undergoing edge deletions. While its static counterpart can be easily
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 (JACM 1981) has been the fastest known algorithm
for three decades. With the loss of a (1 + ε)-approximation factor, the running
time was recently improved to O(n 2+o(1) ) by Bernstein and Roditty (SODA 2011),
and more recently to O(n 1.8+o(1) + m 1+o(1) ) by Henzinger, Krinninger, and Nanongkai
(SODA 2014). In this paper, we finally bring the running time of this case down
to near-linear: We give a (1 + ε)-approximation algorithm with O(m 1+o(1) ) total
update time, thus obtaining near-linear time. Moreover, we obtain O(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 log W) time is the O(mn 0.986 log
W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works
for the general weighted directed case. In contrast to the previous results which
rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called
sparse (d, ε)-hop set introduced by Cohen (JACM 2000) in the PRAM literature.
A (d, ε)-hop set of a graph G = (V, E) is a set E'' of weighted edges such that
the distance between any pair of nodes in G can be (1 + ε)-approximated by their
d-hop distance (given by a path containing at most d edges) on G''=(V, E∪E'').
Our algorithm can maintain an (n o(1) , ε)-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 the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach
tree. It results from extending and combining the monotone Even-Shiloach tree
of Henzinger, Krinninger, and Nanongkai (FOCS 2013) with the bounded-hop SSSP
technique of Bernstein (STOC 2013). These two new tools might be of independent
interest.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
- foaf_Person:
foaf_givenName: Sebastian
foaf_name: Krinninger, Sebastian
foaf_surname: Krinninger
- foaf_Person:
foaf_givenName: Danupon
foaf_name: Nanongkai, Danupon
foaf_surname: Nanongkai
bibo_doi: 10.1109/focs.2014.24
dct_date: 2014^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0272-5428
dct_language: eng
dct_publisher: Institute of Electrical and Electronics Engineers@
dct_title: Decremental single-source shortest paths on undirected graphs in near-linear
total update time@
...