Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей


https://doi.org/10.18255/1818-1015-2013-2-5-22

Полный текст:


Аннотация

В работе строится эффективный ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после удаления одной дуги из ориентированного взвешенного графа. С этой целью вначале описывается используемая структура данных и ее построение, а также приводится 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

Просмотров: 298

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)