An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms

Raj Iyer, David Karger, Hariharan Rahul, Mikkel Thorup
The ACM Journal of Experimental Algorithmics (JEA), Volume 6, 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.

[PDF (448KB)] [PostScript (622KB)] [Gzipped PostScript (134KB)]

Supplement to the paper: Source code and test files (tar.gz, 5MB)

Bibtex Entry:

@article{iyer2001dynconn,
   author =     {Raj Iyer and David Karger and Hariharan Rahul and Mikkel Thorup},
   title =      {An Experimental Study of Poly-Logarithmic, Fully Dynamic, Connectivity Algorithms},
   journal =    {Journal of Experimental Algorithmics},
   volume =     {6},
   year =       {2001},
   issn =       {1084-6654},
   pages =      {4},
   doi =        {http://doi.acm.org/10.1145/945394.945398},
   publisher =  {ACM},
   address =    {New York, NY, USA},
 }