2023-06-02
Deterministic Incremental APSP with polylogarithmic update time and stretch
Publication
Publication
Presented at the
55th Annual ACM Symposium on Theory of Computing, STOC 2023 (June 2023), Orlando, FL, USA
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.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1145/3564246.3585213 | |
| 55th Annual ACM Symposium on Theory of Computing, STOC 2023 | |
|
Forster, S., Nazari, Y., & Probst Gutenberg, M. (2023). Deterministic Incremental APSP with polylogarithmic update time and stretch. In Proceedings of the annual ACM symposium on Theory of Computing (pp. 1173–1186). doi:10.1145/3564246.3585213 |
|
