An Experimental Study of Dynamic Algorithms for Transitive Closure

ABSTRACT

We perform an extensive experimental study of several dynamic algorithms for transitive closure. In particular, we implemented algorithms given by Italiano, Yellin, Cicerone et al., and two recent randomized algorithms by Henzinger and King. We propose a fine-tuned version of Italiano's algorithms as well as a new variant of them, both of which were always faster than any of the other implementations of the dynamic algorithms. We also considered simple-minded algorithms that were easy to implement and likely to be fast in practice. Wetested and compared the above implementations on random inputs, on non-random inputs that are worst-case inputs for the dynamic algorithms, and on an input motivated by a real-world graph.

REFERENCES

• 1: David Alberts , Giuseppe Cattaneo , Giuseppe F. Italiano, An empirical study of dynamic graph algorithms, Journal of Experimental Algorithmics (JEA), 2, p.5-es, 1997 [doi>10.1145/264216.264223]
• 2: Giuseppe Amato , Giuseppe Cattaneo , Giuseppe F. Italiano, Experimental analysis of dynamic minimum spanning tree algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.314-323, January 05-07, 1997, New Orleans, Louisiana, United States
• 3: {3} D. ALBERTS, G. CATTANEO, G. F. ITALIANO, U. NANNI, AND C. ZAROLIAGIS. A software library of dynamic graph algorithms. In <i>Proc. Workshop on Algorithms and Experiments</i>, 1998, 129-136.
• 4: Giorgio Ausiello , Giuseppe F. Italiano , Alberto Marchetti Spaccamela , Umberto Nanni, Incremental algorithms for minimal length paths, Journal of Algorithms, v.12 n.4, p.615-638, Dec. 1991 [doi>10.1016/0196-6774(91)90036-X]
• 5: {5} B. BOLLOBÁS. <i>Random Graphs</i>. Academic Press, New York, 1985.
• 6: {6} T. BATES, E. GERICH, L. JONCHERAY, J-M. JOUANIGOT, D. KARRENBERG, M. TERPSTRA, AND J. YU. Representation of IP routing policies in a routing registry. Technical report, RIPE-181, October 1994.
• 7: {7} S. CHAUDHURI, AND C. ZAROLIAGIS. Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. <i>Algorithmica</i>, 27 (3), 2000, 212-226. Special Issue on Treewidth.
• 8: Serafino Cicerone , Daniele Frigioni , Umberto Nanni , Francesco Pugliese, A uniform approach to semi-dynamic problems on digraphs, Theoretical Computer Science, v.203 n.1, p.69-90, Aug. 6, 1998 [doi>10.1016/S0304-3975(97)00288-0]
• 9: C. Demetrescu , G. F. Italiano, Fully dynamic transitive closure: breaking through the O(n/sup 2/) barrier, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.381, November 12-14, 2000
• 10: Camil Demetrescu , Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study, Proceedings of the 4th International Workshop on Algorithm Engineering, p.218-229, September 05-08, 2000
• 11: {11} H. DJIDJEV, G. PANTZIOU, AND C. ZAROLIAGIS. Improved algorithms for dynamic shortest paths. <i>Algorithmica</i>, 28 (4), 2000, 367-389.
• 12: {12} D. EPPSTEIN, Z. GALIL, G. F. ITALIANO. Dynamic graph algorithms. CRC Handbook of Algorithms and Theory of Computation, Chapter 22, CRC Press, 1999.
• 13: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
• 14: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification I.: planarity testing and minimum spanning trees, Journal of Computer and System Sciences, v.52 n.1, p.3-27, Feb. 1996 [doi>10.1006/jcss.1996.0002]
• 15: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator-Based Sparsification II: Edge and Vertex Connectivity, SIAM Journal on Computing, v.28 n.1, p.341-381, Feb. 1999 [doi>10.1137/S0097539794269072]
• 16: Yossi Shiloach , Shimon Even, An On-Line Edge-Deletion Problem, Journal of the ACM (JACM), v.28 n.1, p.1-4, Jan. 1981 [doi>10.1145/322234.322235]
• 17: Daniele Frigioni , Mario Ioffreda , Umberto Nanni , Giulio Pasqualone, Experimental analysis of dynamic algorithms for the single, Journal of Experimental Algorithmics (JEA), 3, p.5-es, 1998 [doi>10.1145/297096.297147]
• 18: Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Fully dynamic algorithms for maintaining shortest paths trees, Journal of Algorithms, v.34 n.2, p.251-281, Feb. 2000 [doi>10.1006/jagm.1999.1048]
• 19: Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights, Proceedings of the 6th Annual European Symposium on Algorithms, p.320-331, August 24-26, 1998
• 20: Daniele Frigioni , Tobias Miller , Umberto Nanni , Giulio Pasqualone , Guido Schaefer , Christos D. Zaroliagis, An Experimental Study of Dynamic Algorithms for Directed Graphs, Proceedings of the 6th Annual European Symposium on Algorithms, p.368-380, August 24-26, 1998
• 21: {21} A. GORALCIKOVA, AND V. KONBECK. A reduct and closure algorithm for graphs. In <i>Proc. 4th Mathematical Foundations of Computer Science</i>- MFCS'79. <i>Lecture Notes in Computer Science</i>, Vol. 74, 1979, 301-307.
• 22: Monika Rauch Henzinger , Valerie King, Randomized dynamic graph algorithms with polylogarithmic time per operation, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.519-527, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225269]
• 23: M. R. Henzinger , V. King, Fully dynamic biconnectivity and transitive closure, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.664, October 23-25, 1995
• 24: Valerie King, Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.81, October 17-18, 1999
• 25: Valerie King , Garry Sagert, A fully dynamic algorithm for maintaining the transitive closure, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.492-498, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301380]
• 26: G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoretical Computer Science, v.48 n.2-3, p.273-281, Dec., 1986
• 27: Giuseppe F. Italiano, Finding paths and deleting edges in directed acyclic graphs, Information Processing Letters, v.28 n.1, p.5-11, May 30, 1988 [doi>10.1016/0020-0190(88)90136-6]
• 28: Johannes A. La Poutré , Jan van Leeuwen, Maintenance of Transitive Closures and Transitive Reductions of Graphs, Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, p.106-120, July 01, 1987
• 29: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 30: G. Ramalingam , Thomas Reps, On the computational complexity of dynamic graph problems, Theoretical Computer Science, v.158 n.1-2, p.233-277, May 20, 1996 [doi>10.1016/0304-3975(95)00079-8]
• 31: Monika Rauch, Improved data structures for fully dynamic biconnectivity, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.686-695, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195434]
• 32: {32} D. M. YELLIN. Speeding up dynamic transitive closure for bounded degree graphs. <i>Acta Informatica</i>, 30, 1993, 369-384.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Algebraic language theory

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Operations on languages

General Terms:
Algorithms, Theory

Keywords:
dynamic algorithm, experimentation, transitive closure