论文标题
在多个月型时间内完全动态的S-T边缘连接
Fully Dynamic s-t Edge Connectivity in Subpolynomial Time
论文作者
论文摘要
我们提出了一种确定性的完全动态算法，以回答$ n^{o（1）} $最差的情况更新的顶点上的$ c $ - edge连接查询，并查询任何正整数$ c =（\ log n）^{o n）^{o（o）^{o（o（o（log n of））。以前，只有polygarithmic和$ o（\ sqrt {n}）$最差的情况更新时间完全动态算法以回答$ 1 $，$ 2 $和$ 3 $ - 边缘连接查询（Henzinger and thenzinger和King 1995，Frederikson 1997，Galil和Italiano 1991）而闻名。 我们的结果扩展了$ c $ - 边缘连接顶点弹脚[Chalermsook等。 2021]到多层稀疏框架。作为我们的主要技术贡献，我们为多级$ c $ - 边缘连接顶点散布器提供了一种新颖的更新算法，并带有多个单位更新时间。
We present a deterministic fully dynamic algorithm to answer $c$-edge connectivity queries on pairs of vertices in $n^{o(1)}$ worst case update and query time for any positive integer $c = (\log n)^{o(1)}$ for a graph with $n$ vertices. Previously, only polylogarithmic and $O(\sqrt{n})$ worst case update time fully dynamic algorithms were known for answering $1$, $2$ and $3$-edge connectivity queries respectively [Henzinger and King 1995, Frederikson 1997, Galil and Italiano 1991]. Our result extends the $c$-edge connectivity vertex sparsifier [Chalermsook et al. 2021] to a multi-level sparsification framework. As our main technical contribution, we present a novel update algorithm for the multi-level $c$-edge connectivity vertex sparsifier with subpolynomial update time.
