Experimental analysis of dynamic algorithms for the single

ABSTRACT

In this paper we propose the first experimental study of the fully dynamic single-source shortest-paths problem on directed graphs with positive real edge weights. In particular, we perform an experimental analysis of three different algorithms: Dijkstra's algorithm, and the two output bounded algorithms proposed by Ramalingam and Reps in [30] and by Frigioni, Marchetti-Spaccamela and Nanni in [18], respectively. The main goal of this paper is to provide a first experimental evidence for: (<i>a</i>) the effectiveness of dynamic algorithms for shortest paths with respect to a traditional static approach to this problem; (<i>b</i>) the validity of the theoretical model of output boundedness to analyze dynamic graph algorithms. Beside random generated graphs, useful to capture the "asymptotic" behavior of the algorithms, we also developed experiments by considering a widely used graph from the real world, i.e., the Internet graph.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: 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]
• 3: Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
• 4: 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
• 5: 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]
• 6: {6} M. Barbehenn and S. Hutchinson, "Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest-paths trees," <i>IEEE Trans. Robotics and Automation</i> <b>11</b>, 2 (1995), 198-214.
• 7: {7} 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.
• 8: Shiva Chaudhuri , Christos D. Zaroliagis, Shortest Path Queries in Digraphs of Small Treewidth, Proceedings of the 22nd International Colloquium on Automata, Languages and Programming, p.244-255, July 10-14, 1995
• 9: Boris V. Cherkassky , Andrew V. Goldberg, Negative-Cycle Detection Algorithms, Proceedings of the Fourth Annual European Symposium on Algorithms, p.349-363, September 25-27, 1996
• 10: Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.516-525, January 23-25, 1994, Arlington, Virginia, United States
• 11: {11} E. W. Dijkstra, "A note on two problems in connection with graphs," <i>Numerische Mathematik </i> <b>1</b> (1959), 269-271.
• 12: 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]
• 13: {13} S. Even and H. Gazit, "Updating distances in dynamic graphs," <i>Methods of Operations Research</i> <b>49</b> (1985), 371-387.
• 14: Esteban Feuerstein , Alberto Marchetti-Spaccamela, Dynamic algorithms for shortest paths in planar graphs, Theoretical Computer Science, v.116 n.2, p.359-371, Aug. 16, 1993 [doi>10.1016/0304-3975(93)90328-Q]
• 15: Paolo Giulio Franciosa , Daniele Frigioni , Roberto Giaccio, Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs, Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.33-46, February 27-March 01, 1997
• 16: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 17: {17} D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni, "Semi-dynamic algorithms for maintaining single-source shortest-paths trees," <i>Algorithmica</i> <b>22</b>, 3 (1998), 250-274.
• 18: Daniele Frigioni , Alberto Marchetti-Spaccamela , Umberto Nanni, Fully dynamic output bounded single source shortest path problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.212-221, January 28-30, 1996, Atlanta, Georgia, United States
• 19: 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
• 20: {20} A. V. Goldberg and C. Silverstein, "Implementations of Dijkstra's algorithm based on multi-level buckets," Technical Report 95-187, NEC Research Institute, Inc., November 1995.
• 21: {21} A. V. Goldberg and R. E. Tarjan, "Expected performances of Dijkstra's shortest-paths algorithm," Technical Report 96-062, NEC Research Institute, Inc., June 1996.
• 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: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 24: G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoretical Computer Science, v.48 n.2-3, p.273-281, Dec., 1986
• 25: 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]
• 26: Seth M. Malitz, Genus g graphs have pagenumber O g , Journal of Algorithms, v.17 n.1, p.85-109, July 1994 [doi>10.1006/jagm.1994.1028]
• 27: 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]
• 28: {28} K. Mehlhorn, S. Näher, and C. Uhrig. <i>The</i> LEDA <i>User Manual, Version 3.5</i>. Technical report, Max Planck Institut für Informatik, 1997.
• 29: G. Ramalingam , J. van Leeuwen , J. Hartmanis , G. Goos, Bounded Incremental Computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 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: G. Ramalingam , Thomas Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms, v.21 n.2, p.267-305, Sept. 1996 [doi>10.1006/jagm.1996.0046]
• 32: Rajeev Raman, Recent results on the single-source shortest paths problem, ACM SIGACT News, v.28 n.2, p.81-87, June 1997 [doi>10.1145/261342.261352]
• 33: Hans Rohnert, A Dynamization of the All Pairs Least Cost Path Problem, Proceedings of the 2nd Symposium of Theoretical Aspects of Computer Science, p.279-286, January 03-05, 1985
• 34: M. Thorup, Undirected single source shortest paths in linear time, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.12, October 19-22, 1997

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms

Keywords:
dynamic algorithms, experimental analysis of algorithms, shortest paths