Abstract
We have conducted an extensive experimental study on some recent, theoretically outstanding, algorithms for fully dynamic transitive closure along with several variants of them, and compared them to pseudo fully dynamic and simple-minded algorithms developed in a previous study. 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 fully dynamic algorithms can really be of practical value in many situations.
This work was partially supported by the IST Programme (6th FP) of EC under contract No. IST-2002-001907 (integrated project DELIS).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdeddaim, S.: Algorithms and Experiments on Transitive Closure, Path Cover and Multiple Sequence Alignment. In: Proc. 2nd Workshop on Algorithm Engineering and Experiments – ALENEX 2000, pp. 157–169 (2000)
Alberts, D., Cattaneo, G., Italiano, G.F., Nanni, U., Zaroliagis, C.: A Software Library of Dynamic Graph Algorithms. In: Proc. Workshop on Algorithms and Experiments – ALEX 1998, pp. 129–136 (1998)
Demetrescu, C., Emiliozzi, S., Italiano, G.F.: Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms. In: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms – SODA 2004, pp. 362–371 (2004)
Demetrescu, C., Italiano, G.F.: Fully Dynamic Transitive Closure: Breaking through the O(n 2) Barrier. In: Proc. 41st IEEE Symp. on Foundations of Computer Science – FOCS 2000, pp. 381–389 (2000)
Demetrescu, C.: Fully Dynamic Algorithms for Path Problems on Directed Graphs. PhD Thesis, University of Rome “La Sapienza” (February 2001)
Frigioni, D., Miller, T., Nanni, U., Zaroliagis, C.: An Experimental Study of Dynamic Algorithms for Transitive Closure. ACM Journal of Experimental Algorithmics 6(9) (2001)
Henzinger, M.R., King, V.: Fully Dynamic Biconnectivity and Transitive Closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science – FOCS 1995, pp. 664–672 (1995)
Italiano, G.F.: Amortized efficiency of a path retrieval data structure. Theoretical Computer Science 48, 273–281 (1986)
Italiano, G.F.: Finding paths and deleting edges in directed acyclic graphs. Information Processing Letters 28, 5–11 (1988)
King, V.: Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. In: Proc. 40th IEEE Symposium on Foundations of Computer Science – FOCS 1999, pp. 81–91 (1999)
King, V., Sagert, G.: A Fully Dynamic Algorithm for Maintaining the Transitive Closure. In: Proc. 31st ACM Symp. on Theory of Comp., STOC 1999, pp. 492–498 (1999)
King, V., Thorup, M.: A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms. In: Wang, J. (ed.) COCOON 2001. LNCS, vol. 2108, pp. 268–277. Springer, Heidelberg (2001)
Krommidas, I., Zaroliagis, C.: An Experimental Study of Algorithms for Fully Dynamic Transitive Closure. CTI Tech. Report TR 2005/07/01 (July 2005)
Mehlhorn, K., Näher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)
Roditty, L.: A faster and simpler fully dynamic transitive closure. Proc. 14th ACM-SIAM Symp. on Discrete Algorithms – SODA 2003, pp. 404–412 (2003)
Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proc. 43rd IEEE Symposium on Foundations of Computer Science, FOCS 2002, pp. 679–690 (2002)
Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proc. 36th ACM Symp. on Theory of Computing – STOC 2004 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krommidas, I., Zaroliagis, C. (2005). An Experimental Study of Algorithms for Fully Dynamic Transitive Closure. In: Brodal, G.S., Leonardi, S. (eds) Algorithms – ESA 2005. ESA 2005. Lecture Notes in Computer Science, vol 3669. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561071_49
Download citation
DOI: https://doi.org/10.1007/11561071_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29118-3
Online ISBN: 978-3-540-31951-1
eBook Packages: Computer ScienceComputer Science (R0)