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.

, ,
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