论文标题
带有聚类的更新时间和拉伸的确定性增量APSP
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
论文作者
论文摘要
我们提供了第一个确定性数据结构，该数据结构给出了插入边缘插入的加权无方向的图，每个更新都带有polyrogarithmic amortized更新时间和答案查询当前图中任何一对顶点之间的距离，并带有$ o（\ log \ log \ log \ log \ log n）$时间。 在这项工作之前，对于部分动态图，即进行边缘插入或删除的图形不知道数据结构，即使允许对遗忘的对手进行随机化或仅考虑单个源差异，却不在$ n^{o（1）} $更新时间。
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(\log \log n)$ 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 $n^{o(1)}$ update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.
