Incremental computation of shortest paths in semi-dynamic graphs using software components

ABSTRACT

Communication and transportation network topologies routinely change due to link failures and link recovery or due to road construction and blockage. Therefore, the graphs representing these networks are dynamic in nature, i.e., they evolve over time due to edge insertion or deletion. To facilitate computation of shortest paths in dynamic graphs, this paper proposes an object-based software concept with a flexible, incremental interface and outlines its formal specification of behavior. Using this interface, a caller can switch back and forth between the edge insertion and shortest paths computation phases, adding edges, one at a time. Alternative components that implement the interface might amortize and optimize computation of shortest paths in changing graphs and provide interesting performance trade-offs.

REFERENCES

• 1: Giorgio Ausiello , Giuseppe F. Italiano , Alberto Marchetti Spaccamela , Umberto Nanni, Incremental algorithms for minimal length paths, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.12-21, January 22-24, 1990, San Francisco, California, United States
• 2: Antonia Bertolino , Raffaela Mirandola, Software performance engineering of component-based systems, Proceedings of the 4th international workshop on Software and performance, January 14-16, 2004, Redwood Shores, California
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: E. W. Dijkstra, "A note on two problems on connexion with graph", Numerische mathematik 1, 1959, pp. 269--271.
• 5: Donald B. Johnson, A Note on Dijkstra's Shortest Path Algorithm, Journal of the ACM (JACM), v.20 n.3, p.385-388, July 1973 [doi>10.1145/321765.321768]
• 6: 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]
• 7: 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]
• 8: Paolo Narváez , Kai-Yeung Siu , Hong-Yi Tzeng, New dynamic algorithms for shortest path tree computation, IEEE/ACM Transactions on Networking (TON), v.8 n.6, p.734-746, Dec. 2000 [doi>10.1109/90.893870]
• 9: Seth Pettie , Vijaya Ramachandran, Computing shortest paths with comparisons and additions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.267-276, January 06-08, 2002, San Francisco, California
• 10: 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]
• 11: 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]
• 12: Clifford A. Shaffer, A practical introduction to data structures and algorithms analysis, Java edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 13: João Luís Sobrinho, Algebra and algorithms for QoS path computation and hop-by-hop routing in the internet, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.541-550, August 2002 [doi>10.1109/TNET.2002.801397]
• 14: Marulli Sitariman , Bruce Weide, Component-based software using RESOLVE, ACM SIGSOFT Software Engineering Notes, v.19 n.4, p.21-22, Oct. 1994 [doi>10.1145/190679.199221]
• 15: Murali Sitaraman , Bruce W. Weide , Timothy J. Long , William F. Ogden, A Data Abstraction Alternative to Data Structure/Algorithm Modularization, Selected Papers from the International Seminar on Generic Programming, p.102-113, April 27-May 01, 1998
• 16: P. M. Spira and A. Pan, "On Finding and Updating Spanning Trees and Shortest Paths", SIAM J. Computing, Volume 4, No. 3, September 1975, pp. 375--380.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Object-oriented design methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Information hiding
      D.2.4 Software/Program Verification
          Subjects: Formal methods
      D.2.m Miscellaneous

General Terms:
Algorithms, Design, Performance

Keywords:
incremental computation, semi-dynamic graphs, shortest path, software component, specification