Maintaining Minimum Spanning Forests in Dynamic Graphs
Maintaining Minimum Spanning Forests in Dynamic Graphs
复制标题
DOI：
10.1137/s0097539797327209
复制
发表时间：
2002-02
期刊：
影响因子：
--
通讯作者：
Monika Henzinger;Valerie King
中科院分区：
文献类型：
--
作者：
Monika Henzinger;Valerie King
我们提出了第一个在每次操作$o(\sqrt n)$时间内维持最小生成森林的全动态算法。准确地说，该算法每次更新操作使用O（n /3 log n）平摊时间。该算法相当简单且具有确定性。一个直接的结果是第一个完全动态的确定性算法，用于在每次更新的平摊时间O（n1/3 log n）内维护连通性和两部分性，最坏情况下每次查询的时间为O(1)。
We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time $o(\sqrt n)$ per operation. To be precise, the algorithm uses O(n1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and bipartiteness in amortized time O(n1/3 log n) per update, with O(1) worst case time per query.