Maintaining Minimum Spanning Forests in Dynamic Graphs
Authors:
- Monika R. HenzingerMHMonika R. Henzinger
- Valerie KingVKValerie King
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 31 (2) , 364-374
Abstract
We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time $o(\sqrt n)$ per operation. To be precise, the algorithm uses O(n 1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and bipartiteness in amortized time O(n 1/3 log n) per update, with O(1) worst case time per query.
Keywords
This publication has 12 references indexed in Scilit:
- 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
- Dynamic Euclidean minimum spanning trees and extrema of binary functionsDiscrete & Computational Geometry, 1995
- A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graphAlgorithmica, 1992
- Algorithms and Data Structures for an Expanded Family of Matroid Intersection ProblemsSIAM Journal on Computing, 1989
- Data Structures for On-Line Updating of Minimum Spanning Trees, with ApplicationsSIAM Journal on Computing, 1985
- Data Structures and Algorithms 11984
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983
- Data Structures and Network Algorithms1983
- An On-Line Edge-Deletion ProblemJournal of the ACM, 1981