Maintaining minimum spanning forests in dynamic graphs

Citation
Mr. Henzinger et V. King, Maintaining minimum spanning forests in dynamic graphs, SIAM J COMP, 31(2), 2001, pp. 364-374
Citations number
14
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
364 - 374
Database
ISI
SICI code
0097-5397(20011011)31:2<364:MMSFID>2.0.ZU;2-E
Abstract
We present the rst fully dynamic algorithm for maintaining a minimum spanni ng forest in time o(rootn) per operation. To be precise, the algorithm uses O(n(1/3) log n) amortized time per update operation. The algorithm is fair ly simple and deterministic. An immediate consequence is the first fully dy namic deterministic algorithm for maintaining connectivity and bipartitenes s in amortized time O(n(1/3) log n) per update, with O(1) worst case time p er query.