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:Inproceedings
Entered by:
TitleAn Experimental Study of Algorithms for Fully Dynamic Transitive Closure
Bibtex cite IDRACTI-RU1-2005-53
Booktitle 13th Annual European Symposium on Algorithms
Series Lecture Notes in Computer Science
Year published 2005
Volume 3669
Pages 544-555
Organization ESA 2005
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 ID396