Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей
Аннотация
В работе строится эффективный ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после удаления одной дуги из ориентированного взвешенного графа. С этой целью вначале описывается используемая структура данных и ее построение, а также приводится STAR–машина, которая моделирует работу ассоциативных (контекстно–адресуемых) параллельных систем с простыми процессорными элементами и вертикальной обработкой информации. На этой модели ассоциативный параллельный алгоритм представляется в виде главной процедуры DeleteArcSPT, использующей группу вспомогательных процедур для выполнения его отдельных частей. Доказана корректность процедуры DeleteArcSPT и показано, что на STAR-машине она выполняется за время O(hk), где h – число битов, которое требуется для кодирования длины максимального кратчайшего пути, а k – число вершин, для которых вычисляются новые кратчайшие пути после удаления одной дуги из исходного графа.
Об авторе
Анна Шмилевна Непомнящая
Институт вычислительной математики и математической геофизики СО РАН
Россия
Россия
канд. физ.-мат. наук, старший научный сотрудник,
630090, Россия, г. Новосибирск, проспект Академика Лаврентьева, 6
Список литературы
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.
Рецензия
Для цитирования:
Непомнящая А.Ш. Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей. Моделирование и анализ информационных систем. 2013;20(2):5-22. https://doi.org/10.18255/1818-1015-2013-2-5-22
For citation:
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
Просмотров: 698
Послать статью по эл. почте 