Speeding Up Dynamic Shortest-Path Algorithms

References

• Buriol L. S., Resende M. G. C., Ribeiro C. C., Thorup M. A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks (2005) 46:36–56Crossref, Google Scholar
• Cherkassky B. V., Goldberg A. V., Radzik T. Shortest paths algorithms: Theory and experimental evaluation. Math. Programming (1996) 73:129–174Crossref, Google Scholar
• Demetrescu C. Fully dynamic algorithms for path problems on directed graphs. (2001) . PhD thesis, Department of Computer and Systems Science, University of Rome “La Sapienza,” RomeGoogle Scholar
• Demetrescu C., Italiano G. F. Fully dynamic all pairs shortest with real edge weights. Proc. 42nd Annual Sympos. Foundations Comput. Sci. (FOCS 2001) (2001) (IEEE Computer Society, Washington, D.C.) 260–267Crossref, Google Scholar
• Demetrescu C., Italiano G. F. A new approach to dynamic all pairs shortest paths. Proc. 35th Annual ACM Sympos. Theory Comput. (STOC'03) (2003) (ACM Press, New York) 159–166Crossref, Google Scholar
• Demetrescu C., Emiliozzi S., Italiano G. Experimental analysis of dynamic all pairs shortest path algorithms. (2003) . Technical report, Dipartimento di Informatica e Sistemistica, University of Rome “La Sapienza,” RomeGoogle Scholar
• Demetrescu C., Frigioni D., Marchetti-Spaccamela A., Nanni U., Näher S., Wagner D. Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study. Proc. Algorithm Engrg.: 4th Internat. Workshop, WAE 2000 (2000) 1982Saarbrücken, Germany(Springer, Berlin) 218–229Lecture Notes Compu. Sci.Google Scholar
• Dionne R. Etude et extension d'un algorithme de Murchland. INFOR (1978) 16:132–146Google Scholar
• Even S., Shiloach Y. An on-line edge-deletion problem. J. ACM (1981) 28:1–4Crossref, Google Scholar
• Fortz B., Thorup M. Increasing internet capacity using local search. Comput. Optim. Appl. (2004) 29:13–48Crossref, Google Scholar
• Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic output bounded single source shortest path problem. Proc. 7th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (1996) (SIAM, Philadelphia) 212–221Google Scholar
• Frigioni D., Marchetti-Spaccamela A., Nanni U. Semi-dynamic algorithms for maintaining single-source shortest path trees. Algorithmica (1998) 22:250–274Crossref, Google Scholar
• Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithms (2000) 34:351–381Crossref, Google Scholar
• Frigioni D., Ioffreda M., Nanni U., Pasqualone G. Experimental analysis of dynamic algorithms for the single source shortest path problem. ACM J. Experiment. Algorithmics (1998) 3(Article 5):1–20Google Scholar
• Fujishige S. A note on the problem of updating shortest paths. Networks (1981) 11:317–319Crossref, Google Scholar
• Gallo G. Reoptimization procedures in shortest path problems. Rivista di Matematica per le Scienze Economiche e Sociali (1980) 3:3–13Crossref, Google Scholar
• Goto S., Sangiovanni-Vincentelli A. A new shortest path updating algorithm. Networks (1978) 8:341–372Crossref, Google Scholar
• King V., Thorup M. A space saving trick for directed dynamic transitive closure and shortest path algorithms. Proc. 7th Annual Internat. Comput. Combin. Conf. (COCOON). Lecture Notes Comput. Sci. (2001) 2108(Springer Verlag Italia, Milano, Italy) 268–277Crossref, Google Scholar
• Murchland J. D. A fixed matrix method for all shortest distances in a directed graph and for the inverse problem. (1970) . PhD thesis, University of Karlsruhe, Karlsruhe, GermanyGoogle Scholar
• Ramalingam G., Reps T. An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms (1996a) 21:267–305Crossref, Google Scholar
• Ramalingam G., Reps T. On the computational complexity of dynamic graph problems. Theoret. Comput. Sci. (1996b) 158:233–277Crossref, Google Scholar