---
res:
bibo_abstract:
- "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+ϵ)-approximation factor, the running time was
recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we
bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm
with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover,
we obtain m1+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 mn0.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.\r\n\r\nIn contrast
to the previous results, which rely on maintaining a sparse emulator, our algorithm
relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12]
in the PRAM literature. An (h, ϵ)-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+ϵ)-approximated
by their h-hop distance (given by a path containing at most h edges) on G′=(V,
E ∪ F). Our algorithm can maintain an (no(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 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 Mądry [27]. 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.1145/3218657
bibo_issue: '6'
bibo_volume: 65
dct_date: 2018^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0004-5411
- http://id.crossref.org/issn/1557-735X
dct_language: eng
dct_publisher: Association for Computing Machinery@
dct_title: Decremental single-source shortest paths on undirected graphs in near-linear
total update time@
...