Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

2001/07/01 by Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup · 14 citations
Computer Science · #Interconnection Networks and Systems #Advanced Graph Theory Research #Complexity and Algorithms in Graphs

paper · doi:10.1145/502090.502095

openalex publication_date 2001/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

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.

Cited by

• Maintaining information in fully dynamic trees with top trees
• Dynamic Connectivity: Connecting to Networks and Geometry
• The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree
• Recent Advances in Fully Dynamic Graph Algorithms
• Some geometric critical exponents for percolation and the random-cluster model
• Deterministic Dynamic Maximal Matching in Sublinear Update Time
• Fully Dynamic Algorithms for Transitive Reduction
• Percolation on complex networks: Theory and application
• Testing bipartiteness of geometric intersection graphs
• Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
• Faster Deterministic Fully-Dynamic Graph Connectivity
• Worm Monte Carlo study of the honeycomb-lattice loop model
• Minimum spanning tree [wikipedia]
• Top tree [wikipedia]