Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch

Forster, S; Nazari, Y; Gutenberg, MP

Forster, S (通讯作者),Salzburg Univ, Salzburg, Austria.

PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023; (): 1173

Abstract

We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylo......

Full Text Link