Abstract | We have conducted an extensive experimental study on algorithms for fully dynamic transitive
closure. We have implemented the recent fully dynamic algorithms by King [1999], Roditty [2003],
Roditty and Zwick [2002, 2004], and Demetrescu and Italiano [2000, 2005] along with several variants
and compared them to pseudo fully dynamic and simple-minded algorithms developed in a
previous study [Frigioni et al. 2001].We tested and compared these implementations on random inputs,
synthetic (worst-case) inputs, and on inputs motivated by real-world graphs. Our experiments
reveal that some of the dynamic algorithms can really be of practical value in many situations. |