Deterministic algorithms for decremental approximate shortest paths: Faster and Simpler
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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].
Originalsprog | Engelsk |
---|---|
Titel | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |
Redaktører | Shuchi Chawla |
Forlag | Association for Computing Machinery |
Publikationsdato | 2020 |
Sider | 2522-2541 |
ISBN (Elektronisk) | 9781611975994 |
Status | Udgivet - 2020 |
Begivenhed | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, USA Varighed: 5 jan. 2020 → 8 jan. 2020 |
Konference
Konference | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |
---|---|
Land | USA |
By | Salt Lake City |
Periode | 05/01/2020 → 08/01/2020 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics |
ID: 250603806