Deterministic algorithms for decremental approximate shortest paths: Faster and Simpler
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Deterministic algorithms for decremental approximate shortest paths : Faster and Simpler. / Gutenberg, Maximilian Probst; Wulff-Nilsen, Christian.
31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. ed. / Shuchi Chawla. Association for Computing Machinery, 2020. p. 2522-2541.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Deterministic algorithms for decremental approximate 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 - In the decremental (1 + ∈)-Approximate Single-Source ShortEst Path (Sssp) Problem, We Are Given a Graph G = (V, E) With n = |V |, m = |E|, Undergoing Edge Deletions, and a Distinguished Source s ∈ V , and We Are Asked to Process Edge Deletions Efficiently and Answer Queries for Distance EsTimates Dist gG(s, v) for Each v ∈ V , At Any Stage, Such That Distg(s, v) ≤ Dist gG(s, v) ≤ (1 + ∈)Distg(s, v). In The DecreMental (1 + ∈)-Approximate All-Pairs Shortest Path (Apsp) Problem, We Are Asked to Answer Queries for Distance EstiMates Dist gG(u, v) for Every u, v ∈ V . In This Article, We Consider The Problems for Undirected, Unweighted Graphs. We Present a New Deterministic Algorithm for The DecreMental (1 + ∈)-Approximate Sssp Problem That Takes Total Update Time O(Mn0.5+o(1)). Our Algorithm Improves On The Currently Best Algorithm for Dense Graphs By Chechik and Bernstein [Stoc 2016] With Total Update Time Õ(n2) and The Best Existing Algorithm for Sparse Graphs With Running Time Õ(n1.25 √m) [Soda 2017] Whenever m = O(n1.5−o(1)). In Order to Obtain Our New Algorithm, We Develop SevEral New Techniques Including Improved Decremental Cover Data Structures for Graphs, a More Efficient Notion of The Heavy/Light Decomposition Framework Introduced By Chechik and Bernstein and The First Clustering Technique to Maintain a Dynamic Sparse Emulator In The Deterministic SetTing. As a By-Product, We Also Obtain a New Simple DeterMinistic Algorithm for The Decremental (1 + ∈)-Approximate Apsp Problem With Near-Optimal Total Running Time Õ(Mn/∈) matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].
AB - In the decremental (1 + ∈)-Approximate Single-Source ShortEst Path (Sssp) Problem, We Are Given a Graph G = (V, E) With n = |V |, m = |E|, Undergoing Edge Deletions, and a Distinguished Source s ∈ V , and We Are Asked to Process Edge Deletions Efficiently and Answer Queries for Distance EsTimates Dist gG(s, v) for Each v ∈ V , At Any Stage, Such That Distg(s, v) ≤ Dist gG(s, v) ≤ (1 + ∈)Distg(s, v). In The DecreMental (1 + ∈)-Approximate All-Pairs Shortest Path (Apsp) Problem, We Are Asked to Answer Queries for Distance EstiMates Dist gG(u, v) for Every u, v ∈ V . In This Article, We Consider The Problems for Undirected, Unweighted Graphs. We Present a New Deterministic Algorithm for The DecreMental (1 + ∈)-Approximate Sssp Problem That Takes Total Update Time O(Mn0.5+o(1)). Our Algorithm Improves On The Currently Best Algorithm for Dense Graphs By Chechik and Bernstein [Stoc 2016] With Total Update Time Õ(n2) and The Best Existing Algorithm for Sparse Graphs With Running Time Õ(n1.25 √m) [Soda 2017] Whenever m = O(n1.5−o(1)). In Order to Obtain Our New Algorithm, We Develop SevEral New Techniques Including Improved Decremental Cover Data Structures for Graphs, a More Efficient Notion of The Heavy/Light Decomposition Framework Introduced By Chechik and Bernstein and The First Clustering Technique to Maintain a Dynamic Sparse Emulator In The Deterministic SetTing. As a By-Product, We Also Obtain a New Simple DeterMinistic Algorithm for The Decremental (1 + ∈)-Approximate Apsp Problem With Near-Optimal Total Running Time Õ(Mn/∈) matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].
UR - http://www.scopus.com/inward/record.url?scp=85084054022&partnerID=8YFLogxK
M3 - Article in proceedings
AN - SCOPUS:85084054022
SP - 2522
EP - 2541
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: 250603806