research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:chita
TitleAn Experimental Study of Algorithms for Fully Dynamic Transitive Closure
Bibtex cite IDRACTI-RU1-2008-39
Journal ACM Journal of Experimental Algorithmics
Year published 2008
Volume 12
Number 1.6
Pages 1-22
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.
Krommudas, I.
Zaroliagis, Christos
J26-KZ-ACM-JEA-Vol12-N1.6-2008.pdf (main file)
Publication ID487