Dynamic Connectivity in Graphs: Theory and Practice
David Alberts:
Dynamic Connectivity in Graphs: Theory and Practice
Kurzbeschreibung
Referenzen
D. Alberts. Implementation of the dynamic connectivity algorithm by Monika Rauch Henzinger and Valerie King. TR B 95-10, Freie Universität Berlin, Inst. f. Informatik, 1995.
D. Alberts, G. Cattaneo, G. F. Italiano. An empirical study of dynamic graph algorithms. In Proc. 7th SODA, p. 192 - 201, 1996.
D. Alberts, M. R. Henzinger. Average case analysis of dynamic graph algorithms. In Proc. 6th SODA, p. 312 - 321, 1995. (Technical Report)
D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. In Proc. 33rd FOCS,p. 60 - 69, 1992.
G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput., 14:781 - 798, 1985.
M. R. Henzinger, V. King. Randomized dynamic graph algorithms with polylogarithmic time per operartion. In Proc. 27th STOC, p. 519 - 527, 1995.
