Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree
https://doi.org/10.18255/1818-1015-2013-2-5-22
Abstract
The paper proposes an efficient associative algorithm for dynamic update of the shortest paths tree of a directed weighted graph after deleting an edge. To this end, we provide the data structure and its building along with the STAR–machine that simulates the run of associative (content–addressable) parallel systems with simple single–bit processing elements and vertical processing. The associative algorithm is represented on the STAR–machine as the main procedure DeleteArcSPT that uses some auxiliary procedures. By means of the auxiliary procedures, we execute some parts of the associative parallel algorithm for dynamic update of the shortest paths tree after deleting an arc from the graph. We prove correctness of the procedure DeleteArcSPT and all its parts. We obtain that on the STAR–machine this procedure takes O(hk) time, where h is the number of bits required for coding the maximum of the shortest paths weights and k is the number of vertices, whose shortest paths change after deleting an edge from the given graph.
About the Author
A. S. Nepomniaschaya
Institute of Computational Mathematics and Mathematical Geophysics SB RAS
Russian Federation
Russian Federation
канд. физ.-мат. наук, старший научный сотрудник,
prospect Akademika Lavrentjeva, 6, Novosibirsk, 630090, Russia
References
1. Ramalingam G. Bounded Incremental Computation // Lecture Notes in Computer Science. Berlin: Springer–Verlag, 1996. Vol. 1089. P. 30–51.
2. Ramalingam G., Reps T. An incremental algorithm for a generalization of the shortest paths problem // Journal of Algorithms. Academic Press. 1996. Vol. 21. P. 267–305.
3. Frigioni D., Marchetti-Spaccamela A., Nanni U. Semi–dynamic algorithms for maintaining single source shortest paths trees // Algorithmica. Berlin: Springer–Verlag, 1998. Vol. 25. P. 250–274.
4. Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic algorithms for maintaining shortest paths trees // Journal of Algorithms. Academic Press. 2000. Vol. 34. P. 351–381.
5. Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic shortest paths in digraphs with arbitrary arc weights // Journal of Algorithms. Elsevier Science. 2003. Vol. 49. P. 86–113.
6. Nepomniaschaya A. S. Associative version of the Ramalingam decremental algorithm for dynamic updating the single-sink shortest paths subgraph // Proc. of the 10-th International Conference on Parallel Computing Technologies, PaCT-2009, Novosibirsk, Russia. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2009. Vol. 5698. P. 257–268.
7. Nepomniaschaya A. S. Language STAR for associative and parallel computation with vertical data processing // Proc. of the International Conference “Parallel Computing Technologies”. World Scientific, Singapore, 1991. P. 258–265.
8. Dijkstra E.W. A note on two problems in connection with graphs // Numerische Mathematik. 1959. Vol. 1. P. 269–271.
9. Foster C.C. Content Addressable Parallel Processors. New York: Van Nostrand Reinhold Company, 1976.
10. Непомнящая А.Ш., Владыко М. А. Сравнение моделей ассоциативных параллельных вычислениний // Программирование. 1997. № 6. С. 41–50 (English transl.: Nepomniaschaya A.Sh., Vladyko M.A. A Comparison of Associative Computation Models //Programming and Computer Software. 1997. V. 23, № 6. P. 319–324).
11. Nepomniaschaya A. S. Solution of path problems using associative parallel processors // Proc. of the Intern. Conf. on Parallel and Distributed Systems, ICPADS’97. Korea, Seoul, IEEE Computer Society Press, 1997. P. 610–617.
12. Nepomniaschaya A. S., Dvoskina M. A. A simple implementation of Dijkstra’s shortest path algorithm on associative parallel processors // Fundamenta Informaticae. IOS Press, 2000. Vol. 43. P. 227-243.
13. Nepomniaschaya A. S. Simultaneous finding the shortest paths and distances in directed graphs using associative parallel processors // Proc. of the Intern. Conf. “Information Visualization (IV 2003). England, London, IEEE Computer Society, Los Alamitos, 2003. P. 665–670.
Review
For citations:
Nepomniaschaya A.S. Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree. Modeling and Analysis of Information Systems. 2013;20(2):5-22. (In Russ.) https://doi.org/10.18255/1818-1015-2013-2-5-22
Views:
903
Email this article 