An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
We present an experimental study of different variants of theamortized <i>O</i>(log<sup>2</sup> <i>n</i>)-time fully-dynamicconnectivity algorithm of Holm, de Lichtenberg, and Thorup(STOC'98). The experiments build upon experiments provided byAlberts, Cattaneo, and Italiano (SODA'96) on the randomizedamortized <i>O</i>(log<sup>3</sup> <i>n</i>) fully-dynamicconnectivity algorithm of Henzinger and King (STOC'95). Ourexperiments shed light upon similarities and differences betweenthe two algorithms. We also present a slightly modified version ofthe Henzinger-King algorithm that runs in <i>O</i>(log<sup>2</sup><i>n</i>) time, which resulted from our experiments.