Fully-dynamic minimum spanning forest with improved worst-case update time
Fully-dynamic minimum spanning forest with improved worst-case update time
复制标题
全动态最小生成森林，改进了最坏情况的更新时间
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Christian Wulff
中科院分区：
文献类型：
--
作者：
Christian Wulff
我们给出了一个拉斯维加斯的数据结构，保持一个最小生成森林的n-顶点边加权无向动态图进行更新，包括任何混合的边插入和删除。每次更新的最坏情况时间为O（n1/2 - c）w. h. p.，其中c > 0是某个常数，并且这个界限也在预期中成立。这是第一个数据结构，实现了O（n）的确定性最坏情况更新时间的改进Eppstein等人，这一束缚已经持续了25年事实上，以前甚至不知道如何在最坏情况下以多项式方式比Θ（θ n）更快地维护未加权图的生成森林。我们的结果是通过首先给出一个减少从全动态到递减最小生成森林保存最坏情况下的更新时间对数因子。然后递减最小生成森林解决了使用几种新的技术，其中之一涉及跟踪低电导削减动态图。我们的结果的直接推论是第一个用于全动态连接的拉斯维加斯数据结构，其中每个更新在最坏情况下的时间多项式中处理，比Θ（n）w. h. p.快;这个数据结构的最坏情况查询时间为O（1）。
We give a Las Vegas data structure which maintains a minimum spanning forest in an n-vertex edge-weighted undirected dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O(n1/2 - c) worst-case time w.h.p. where c > 0 is some constant, and this bound also holds in expectation. This is the first data structure achieving an improvement over the O(√n) deterministic worst-case update time of Eppstein et al., a bound that has been standing for 25 years. In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than Θ(√n). Our result is achieved by first giving a reduction from fully-dynamic to decremental minimum spanning forest preserving worst-case update time up to logarithmic factors. Then decremental minimum spanning forest is solved using several novel techniques, one of which involves keeping track of low-conductance cuts in a dynamic graph. An immediate corollary of our result is the first Las Vegas data structure for fully-dynamic connectivity where each update is handled in worst-case time polynomially faster than Θ(√n) w.h.p.; this data structure has O(1) worst-case query time.