A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs. / Das, Debarati; Gutenberg, Maximilian Probst; Wulff-Nilsen, Christian.
ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. Association for Computing Machinery, Inc., 2022. p. 3482-3495.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
AU - Das, Debarati
AU - Gutenberg, Maximilian Probst
AU - Wulff-Nilsen, Christian
N1 - Publisher Copyright: Copyright © 2022 by SIAM.
PY - 2022
Y1 - 2022
N2 - In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph G undergoes a sequence of edge weight updates and the goal is to maintain a data structure on G, that can quickly answer distance queries between any two vertices x,y ? V(G). The currently best algorithms [FOCS'01, SODA'05] for this problem require Õ(n2/3) worst-case update and query time, while conditional lower bounds [FOCS'16] show that either update or query time is needed1. In this article, we present the first algorithm with near-optimal worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an online algorithm for the incremental APSP problem with worst-case update/query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem.
AB - In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph G undergoes a sequence of edge weight updates and the goal is to maintain a data structure on G, that can quickly answer distance queries between any two vertices x,y ? V(G). The currently best algorithms [FOCS'01, SODA'05] for this problem require Õ(n2/3) worst-case update and query time, while conditional lower bounds [FOCS'16] show that either update or query time is needed1. In this article, we present the first algorithm with near-optimal worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an online algorithm for the incremental APSP problem with worst-case update/query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem.
UR - http://www.scopus.com/inward/record.url?scp=85127299237&partnerID=8YFLogxK
U2 - 10.1137/1.9781611977073.138
DO - 10.1137/1.9781611977073.138
M3 - Article in proceedings
AN - SCOPUS:85127299237
SP - 3482
EP - 3495
BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PB - Association for Computing Machinery, Inc.
T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Y2 - 9 January 2022 through 12 January 2022
ER -
ID: 340107574