David Alberts

Dynamic Connectivity in Graphs: Theory and Practice

Betreuer: Emo Welzl
Abschluss: PhD
Abgabedatum: 15.02.1996
Homepage des Autors:



  1. 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.
  2. D. Alberts, G. Cattaneo, G. F. Italiano. An empirical study of dynamic graph algorithms. In Proc. 7th SODA, p. 192 - 201, 1996.
  3. D. Alberts, M. R. Henzinger. Average case analysis of dynamic graph algorithms. In Proc. 6th  SODA, p. 312 - 321, 1995. (Technical Report)
  4. 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.
  5. G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput., 14:781 - 798, 1985.
  6. M. R. Henzinger, V. King. Randomized dynamic graph algorithms with polylogarithmic time per operartion. In Proc. 27th STOC, p. 519 - 527, 1995.