An empirical study of dynamic graph algorithms

ABSTRACT

The contributions of this paper are both of theoretical and of experimental nature. From the experimental point of view, we conduct an empirical study on some dynamic connectivity algorithms which where developed recently. In particular, the following implementations were tested and compared with simple algorithms: simple sparsification by Eppstein et al. and the recent randomized algorithm by Henzinger and King. In our experiments, we considered both random and non-random inputs. Moreover, we present a simplified variant of the algorithm by Henzinger and King, which for random inputs was always faster than the original implementation. For non-random inputs, simple sparsification was the fastest algorithm for small sequences of updates; for medium and large sequences of updates, the original algorithm by Henzinger and King was faster.From the theoretical point of view, we analyze the average case running time of simple sparsification and prove that for dynamic random graphs its logarithmic overhead vanishes.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: {2} D. Alberts. Implementation of the dynamic connectivity algorithm by Henzinger and King. TR B 95-10, Freie Universität Berlin, Inst. f. Informatik, 1995.
• 3: David Alberts , Giuseppe Cattaneo , Giuseppe F. Italiano, An empirical study of dynamic graph algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.192-201, January 28-30, 1996, Atlanta, Georgia, United States
• 4: David Alberts , Monika Rauch Henzinger, Average case analysis of dynamic graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.312-321, January 22-24, 1995, San Francisco, California, United States
• 5: 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
• 6: {6} N. Alon and J. H. Spencer. <i>The Probabilistic Method</i>. J. Wiley & Sons, New York, 1991.
• 7: {7} B. Bollobás. <i>Random Graphs</i>. Academic Press, London, 1985.
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: {9} E. A. Dinitz, "Maintaining the 4-edge-connected components of a graph on-line", <i>Proc. 2nd Israel Symp. on Theory of Computing and Systems</i> (1993), 88-99.
• 10: David Eppstein, Average case analysis of dynamic geometric optimization, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.77-86, January 23-25, 1994, Arlington, Virginia, United States
• 11: {11} D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig, "Sparsification--A technique for speeding up dynamic graph algorithms", <i>Proc. 33rd IEEE Symp. on Foundations of Computer Science</i> (1992), 60-69.
• 12: {12} D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig, "Sparsification--A technique for speeding up dynamic graph algorithms", full version. Manuscript, revised 1995.
• 13: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification for dynamic planar graph algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.208-217, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167159]
• 14: {14} G.N. Frederickson, "Data structures for on-line updating of minimum spanning trees, with applications", <i>SIAM J. Comput.</i> 14 (1985), 781-798.
• 15: Greg N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, Proceedings of the 32nd annual symposium on Foundations of computer science, p.632-641, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185429]
• 16: Zvi Galil , Giuseppe F. Italiano, Maintaining the 3-edge-connected components of a graph on-line, SIAM Journal on Computing, v.22 n.1, p.11-28, Feb. 1993 [doi>10.1137/0222002]
• 17: {17} M. R. Henzinger. Fully dynamic cycle equivalence in graphs. <i>Proc. 35th IEEE Symp. Foundations of Computer Science</i> (1994), 744-755.
• 18: {18} M. R. Henzinger. Personal communication. 1995.
• 19: 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]
• 20: Monika Rauch Henzinger , Mikkel Thorup, Improved Sampling with Applications to Dynamic Graph Algorithms, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.290-299, July 08-12, 1996
• 21: Arkady Kanevsky , Roberto Tamassia , Giuseppe Di Battista , Jianer Chen, On-line maintenance of the four-components of a graph (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.793-801, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185451]
• 22: Johannes A. La Poutré, Maintenance of Triconnected Components of Graphs (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.354-365, July 13-17, 1992
• 23: J. A. La Poutré , J. van Leeuwen , M. H. Overmars, Maintenance of 2- and 3-edge-connected components of graphs I, Discrete Mathematics, v.114 n.1-3, p.329-359, April 28, 1993 [doi>10.1016/0012-365X(93)90376-5]
• 24: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Communications of the ACM, v.38 n.1, p.96-102, Jan. 1995 [doi>10.1145/204865.204889]
• 25: Ketan Mulmuley, Randomized multidimensional search trees (extended abstract): dynamic sampling, Proceedings of the seventh annual symposium on Computational geometry, p.121-131, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109662]
• 26: {26} K. Mulmuley, <i>Computational Geometry, an Introduction through Randomized Algorithms</i>, Prentice Hall, 1993.
• 27: {27} H. Nagamochi, T. Ibaraki, "Linear time algorithms for finding a sparse <i>k</i>-connected spanning subgraph of a <i>k</i>-connected graph", <i>Algorithmica</i>, 7 (1992), 583-596.
• 28: {28} S. Näher, LEDA User Manual, Version 3.0, Technical Report, Max-Planck-Institut für Informatik, 1994.
• 29: Ganesan Ramalingam, Bounded incremental computation, University of Wisconsin at Madison, Madison, WI, 1993
• 30: {30} M. Rauch, "Fully dynamic biconnectivity in graphs", <i>Proc. 33rd IEEE Symp. Foundations of Computer Science</i> (1992), 50-59.
• 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} O. Schwarzkopf, "Dynamic Maintenance of Convex Polytopes and Related Structures". Ph.D. Thesis, Freie Universität Berlin, 1992.
• 33: {33} J. Westbrook and R. E. Tarjan, "Maintaining bridge-connected and biconnected components on-line", <i>Algorithmica</i> 7 (1992), 433-464.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms