%0 Journal Article %1 holm-poly-logarithmid-dynamic-mst-2001 %A Holm, Jacob %A de Lichtenberg, Kristian %A Thorup, Mikkel %C New York, NY, USA %D 2001 %I ACM %J J. ACM %K clustering mst %N 4 %P 723--760 %R 10.1145/502090.502095 %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 <i>n</i> vertices, the amortized operation costs are <i>O</i>(log² <i>n</i>) for connectivity, <i>O</i>(log⁴ <i>n</i>) for minimum spanning forest, 2-edge connectivity, and <i>O</i>(log⁵ <i>n</i>) biconnectivity.

@article{holm-poly-logarithmid-dynamic-mst-2001, 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 <i>n</i> vertices, the amortized operation costs are <i>O</i>(log² <i>n</i>) for connectivity, <i>O</i>(log⁴ <i>n</i>) for minimum spanning forest, 2-edge connectivity, and <i>O</i>(log⁵ <i>n</i>) biconnectivity.}, acmid = {502095}, added-at = {2016-07-12T19:24:18.000+0200}, address = {New York, NY, USA}, author = {Holm, Jacob and de Lichtenberg, Kristian and Thorup, Mikkel}, biburl = {https://www.bibsonomy.org/bibtex/2321b8060dfd1c11f0b0b6635ece70b9b/mhwombat}, description = {Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity}, doi = {10.1145/502090.502095}, interhash = {b97f78f55bc91df915b0ed235ab4b4ec}, intrahash = {321b8060dfd1c11f0b0b6635ece70b9b}, issn = {0004-5411}, journal = {J. ACM}, keywords = {clustering mst}, month = jul, number = 4, numpages = {38}, pages = {723--760}, publisher = {ACM}, timestamp = {2016-07-12T19:25:30.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 }