Maintaining minimum spanning forests in dynamic graphs
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(n1/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(n1/3 log n) per update, with O(1) worst case time per query.
Keywords: Data structure ; Dynamic graph ; Graph algorithm ; Minimum spanning tree ; Algorithms ; Data structures ; Problem solving ; Query languages ; Theorem proving ; Trees (mathematics) ; Dynamic graphs ; Computational complexity
Record created on 2007-01-18, modified on 2016-08-08