Near-optimal fully-dynamic graph connectivity
Near-optimal fully-dynamic graph connectivity
复制标题
DOI：
10.1145/335305.335345
复制
发表时间：
2000-05
期刊：
影响因子：
--
通讯作者：
M. Thorup
中科院分区：
文献类型：
--
作者：
M. Thorup
本文给出了最基本的非平凡全动态图问题--全动态图连通度的近最优界。支持连接查询的时间复杂度为O（log n/log log log n），而支持更新的时间复杂度为O（log n（log log n）3）。时间复杂度是O（（log n）2）。我们的新界是一般细胞探针下界f2（log n~ log log n）的双对数因子。我们的算法在指针机器上运行，并且仅使用标准AC °指令。在我们的发展中，我们做了一些比较琐碎的观察，改善了一些确定性的界限。将原连通性算法的空间上界从O（m + nlogn）改进为O（m）.该算法的时间复杂度从原来的O（（logn）4）提高到O（（logn）3loglogn）.
In this paper we present near-optimal bounds for fullydynamic graph connectivity which is the most basic nontrivial fully-dynamic graph problem. Connectivity queries are supported in O(log n/log log log n) time while the updates are supported in O(log n(log log n) 3) expected amortized time. The previous best update time was O((log n)2). Our new bound is only doubly-logarithmic factors from a general cell probe lower bound of f2(log n~ log log n). Our algorithm runs on a pointer machine, and uses only standard AC ° instructions. In our developments we make some comparatively trivial observations improving some deterministic bounds. The space bound of the previous O((log n) ~) connectivity algorithm is improved from O(m + n log n) to O(m). The previous time complexity of fully-dynamic 2-edge and biconnectivity is improved from O((log n) 4) to O((log n) 3 log log n).