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.


Published in:
SIAM J Comput, 31, 2, 364-374
Year:
2001
Keywords:
Other identifiers:
Scopus: 2-s2.0-0036253382
Laboratories:




 Record created 2007-01-18, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)