Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- 1 July 2001
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 48 (4), 723-760
- https://doi.org/10.1145/502090.502095
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.Keywords
This publication has 23 references indexed in Scilit:
- Unique Maximum Matching AlgorithmsJournal of Algorithms, 2001
- Efficient Algorithms for Petersen's Matching TheoremJournal of Algorithms, 2001
- Decremental Dynamic ConnectivityJournal of Algorithms, 1999
- Randomized fully dynamic graph algorithms with polylogarithmic time per operationJournal of the ACM, 1999
- Sparsification—a technique for speeding up dynamic graph algorithmsJournal of the ACM, 1997
- Fully dynamic biconnectivity in graphsAlgorithmica, 1995
- Complexity models for incremental computationTheoretical Computer Science, 1994
- Maintaining bridge-connected and biconnected components on-lineAlgorithmica, 1992
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975