Fully-dynamic all-pairs shortest paths: Improved worst-case time and space bounds
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Fully-dynamic all-pairs shortest paths : Improved worst-case time and space bounds. / Gutenberg, Maximilian Probst; Wulff-Nilsen, Christian.
31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. red. / Shuchi Chawla. Association for Computing Machinery, 2020. s. 2562-2574.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Fully-dynamic all-pairs shortest paths
T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
AU - Gutenberg, Maximilian Probst
AU - Wulff-Nilsen, Christian
PY - 2020
Y1 - 2020
N2 - Given a directed weighted graph G = (V, E) undergoing vertex insertions and deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of G. In two breakthrough results, Italiano and Demetrescu [STOC'03] presented an algorithm that requires Õ(n2) amortized update time, and Thorup showed in [STOC'05] that worst-case update time Õ(n2+3/4) can be achieved. In this article, we make substantial progress on the problem. We present the following new results: • We present the first deterministic data structure that breaks the Õ(n2+3/4) worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to Õ(n2+5/7) = Õ(n2.71..) and to Õ(n2+3/5) = Õ(n2.6) for unweighted graphs. • We present a simple deterministic algorithm with Õ(n2+3/4) worst-case update time (Õ(n2+2/3) for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time Õ(n2+2/3) (Õ(n2+1/2) for unweighted graphs) that works against a non-oblivious adversary. Both data structures require space Õ(n2). These are the first exact dynamic algorithms with truly-subcubic update time and space usage. This makes significant progress on an open question posed in multiple articles [COCOON'01, STOC'03, ICALP'04, Encyclopedia of Algorithms'08] and is critical to algorithms in practice [TALG'06] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time [SODA'17].
AB - Given a directed weighted graph G = (V, E) undergoing vertex insertions and deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of G. In two breakthrough results, Italiano and Demetrescu [STOC'03] presented an algorithm that requires Õ(n2) amortized update time, and Thorup showed in [STOC'05] that worst-case update time Õ(n2+3/4) can be achieved. In this article, we make substantial progress on the problem. We present the following new results: • We present the first deterministic data structure that breaks the Õ(n2+3/4) worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to Õ(n2+5/7) = Õ(n2.71..) and to Õ(n2+3/5) = Õ(n2.6) for unweighted graphs. • We present a simple deterministic algorithm with Õ(n2+3/4) worst-case update time (Õ(n2+2/3) for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time Õ(n2+2/3) (Õ(n2+1/2) for unweighted graphs) that works against a non-oblivious adversary. Both data structures require space Õ(n2). These are the first exact dynamic algorithms with truly-subcubic update time and space usage. This makes significant progress on an open question posed in multiple articles [COCOON'01, STOC'03, ICALP'04, Encyclopedia of Algorithms'08] and is critical to algorithms in practice [TALG'06] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time [SODA'17].
UR - http://www.scopus.com/inward/record.url?scp=85084090669&partnerID=8YFLogxK
M3 - Article in proceedings
AN - SCOPUS:85084090669
SP - 2562
EP - 2574
BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
A2 - Chawla, Shuchi
PB - Association for Computing Machinery
Y2 - 5 January 2020 through 8 January 2020
ER -
ID: 250488073