Deterministic fully dynamic graph algorithms are presented for connectivity, minimum
spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a
graph with n vertices, the amortized operation costs are O(log 2 n) for connectivity, O(log 4 n) for
minimum spanning forest, 2-edge connectivity, and O(log 5 n) biconnectivity.
%0 Journal Article
%1 holm2001polylogarithmic
%A Holm, Jacob
%A De Lichtenberg, Kristian
%A Thorup, Mikkel
%A Thorup, Mikkel
%D 2001
%I Citeseer
%J Journal of the ACM (JACM)
%K algorithms connectivity dynamic_graphs graph_theory
%N 4
%P 723--760
%T Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
%U http://doi.acm.org/10.1145/502090.502095
%V 48
%X Deterministic fully dynamic graph algorithms are presented for connectivity, minimum
spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a
graph with n vertices, the amortized operation costs are O(log 2 n) for connectivity, O(log 4 n) for
minimum spanning forest, 2-edge connectivity, and O(log 5 n) biconnectivity.
@article{holm2001polylogarithmic,
abstract = {Deterministic fully dynamic graph algorithms are presented for connectivity, minimum
spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a
graph with n vertices, the amortized operation costs are O(log 2 n) for connectivity, O(log 4 n) for
minimum spanning forest, 2-edge connectivity, and O(log 5 n) biconnectivity.},
added-at = {2019-09-12T19:22:16.000+0200},
author = {Holm, Jacob and De Lichtenberg, Kristian and Thorup, Mikkel and Thorup, Mikkel},
biburl = {https://www.bibsonomy.org/bibtex/2e7f4e79b4d2958d7cdc65f6f823e8480/peter.ralph},
interhash = {b97f78f55bc91df915b0ed235ab4b4ec},
intrahash = {e7f4e79b4d2958d7cdc65f6f823e8480},
journal = {Journal of the ACM (JACM)},
keywords = {algorithms connectivity dynamic_graphs graph_theory},
number = 4,
pages = {723--760},
publisher = {Citeseer},
timestamp = {2019-09-12T19:22:16.000+0200},
title = {Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity},
url = {http://doi.acm.org/10.1145/502090.502095},
volume = 48,
year = 2001
}