An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
Raj D. Iyer, David R. Karger, Hariharan Shankar Rahul, Mikkel Thorup · ACM Journal of Experimental Algorithmics · 2001
We present an experimental study of different variants of the amortized O (log 2 n )-time fully-dynamic connectivity algorithm of Holm, de Lichtenberg, and Thorup (STOC'98). The experiments build upon experiments provided by Alberts, Cattaneo, and Italiano (SODA'96) on the randomized amortized O (log 3 n ) fully-dynamic connectivity algorithm of Henzinger and King (STOC'95). Our experiments shed light upon similarities and differences between the two algorithms. We also present a slightly modified version of the Henzinger-King algorithm that runs in O (log 2 n ) time, which resulted from our experiments.