Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
OPEN ACCESS
Loading...
Author / Producer
Date
2023-06-02
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in O(loglogn) time. Prior to this work, no data structure was known for partially dynamic graphs, i.e., graphs undergoing either edge insertions or deletions, with less than no(1) update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.
Permanent link
Publication status
published
External links
Book title
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
Journal / series
Volume
Pages / Article No.
1173 - 1186
Publisher
Association for Computing Machinery
Event
55th Annual ACM Symposium on Theory of Computing (STOC '23)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Dynamic algorithms; Shortest paths; Graph algorithms
Organisational unit
09687 - Kyng, Rasmus / Kyng, Rasmus
Notes
Funding
204787 - Algorithms and complexity for high-accuracy flows and convex optimization (SNF)