Lazy shortest path computation in dynamic graphs

• Autorzy: Aioanei D.
• Języki publikacji: EN

Abstrakty

EN

We address the problem of single-source shortest path computation in digraphs with non-negative edge weights subjected to frequent edge weight decreases such that only some shortest paths are requested in-between updates. We optimise a recent semidynamic algorithm for weight decreases previously reported to be the fastest one in various conditions, resulting in important time savings that we demonstrate for the problem of incremental path map construction in usersteered image segmentation. Moreover, we extend the idea of lazy shortest path computation to digraphs subjected to both edge weight increases and decreases, comparing favourably to the fastest recent state-of-the-art algorithm.

Słowa kluczowe

EN

single-source shortest path; dynamic graph; livewire; active snake; interactive image segmentation

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2012
• Tom: Vol. 13 (3)
• Strony: 113--137
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Aioanei D.

• Department of Biochemistry "G. Moruzzi", University of Bologna, Via Irnerio 48, 40126 Bologna, Italy,

Bibliografia

• [1] Chan E.P. F., Yang Y.: Shortest path tree computation in dynamic graphs. IEEE Trans. Comput., 58(4):541–557, 2009.
• [2] Dijkstra E. W.: A Note on Two Problems in Connection with Graphs. Numerical Mathematics, 1:269–271, 1959.
• [3] Falcao A. X., Udupa J. K., Miyazawa F. K.: An ultra-fast user-steered image segmentation paradigm: live wire on the fly. IEEE transactions on medical imaging, 19(1):55–62, 2000.
• [4] Falcao A. X., Udupa J. K., Samarasekera S., Sharma S., Hirsch B. E., de A. Lotufo R.: User-steered image segmentation paradigms: Live wire and live lane. Graphical Models and Image Processing, 60(4):233 – 260, 1998.
• [5] Faloutsos M., Faloutsos P., Faloutsos C.: On power-law relationships of the internet topology. In SIGCOMM ’99: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, pp. 251–262, New York, NY, USA, 1999. ACM. 136 Daniel Aioanei
• [6] Federal Highway Administration (FHWA).: The National Highway Planning Network, 08 2005.
• [7] Frigioni D., Ioffreda M., Nanni U., Pasqualone G.: Experimental analysis of dynamic algorithms for the single source shortest path problem. J. Exp. Algorithmics, 3:5, 1998.
• [8] Frigioni D., Marchetti-Spaccamela A., Nanni U.: Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithms, 34(2):251–281, 2000.
• [9] Kang H. W.: G-wire: a livewire segmentation algorithm based on a generalized graph formulation. Pattern Recogn. Lett., 26(13):2042–2051, 2005.
• [10] Kang H. W., Shin S. Y.: Enhanced lane: interactive image segmentation by incremental path map construction. Graph. Models, 64(5):282–303, 2002.
• [11] Meijering E., Jacob M., Sarria J.-C. F., Steiner P., Hirling H., Unser M.: Design and validation of a tool for neurite tracing and analysis in fluorescence microscopy images. Cytometry. Part A: the journal of the International Society for Analytical Cytology, 58(2):167–176, 2004.
• [12] Mortensen E. N., Barrett W. A.: Intelligent scissors for image composition. In SIGGRAPH ’95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, pp. 191–198, New York, NY, USA, 1995. ACM.
• [13] Moy J. T.: OSPF: Anatomy of an Internet Routing Protocol. Addison-Wesley Professional, New York, 1998.
• [14] Narv´aez P., Siu K.-Y., Tzeng H.-Y.: New dynamic algorithms for shortest path tree computation. IEEE/ACM Trans. Netw., 8(6):734–746, 2000.
• [15] Narv´aez P., Siu K.-Y., Tzeng H.-Y.: New dynamic spt algorithm based on a balland- string model. IEEE/ACM Trans. Netw., 9(6):706–718, 2001.
• [16] Perlman R.: A comparison between two routing protocols: OSPF and IS-IS. IEEE Network, 5(5):18–24, 1991.
• [17] Ramalingam G., Reps T.: An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms, 21(2):267–305, 1996.
• [18] Steiniger S., Bocher E.: An overview on current free and open source desktop GIS developments. International Journal of Geographical Information Science, 23(10):1345–1370, 2009.
• [19] Zhan F. B., Noon C. E.: Shortest path algorithms: An evaluation using real road networks. Transportation Science, 32(1):65–73, January 1998.