Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch

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 (loglog n ) time.

Authors

• Sebastian Forster
• Yasamin Nazari
• Maximilian Probst Gutenberg

Keywords

• Dynamic algorithms
• Graph algorithms
• Shortest Paths