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

doi:10.17223/20710410/46/5

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги	2 MB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/46/5

#матрица смежности

#аффектная вершина

#вертикальная обработка данных

#ориентированные взвешенные графы

#инкрементальные алгоритмы

#ассоциативные параллельные процессоры

Title: Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги
Title: Associative parallel algorithm for dynamic update of shortest paths tree after inserting an ARC
Creator: Непомнящая, Анна Шмилевна
|
Снытникова, Татьяна Валентиновна
Date: 2019
DOI: 10.17223/20710410/46/5
Description: Строится ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги к ориентированному взвешенному графу. Кратко описывается STAR-машина, которая моделирует работу ассоциативных (контекстно-адресуемых) параллельных систем с простейшими процессорными элементами и вертикальной обработкой информации. Описывается используемая структура данных и её свойства. Ассоциативный параллельный алгоритм представляется в виде процедуры InsertArcSPT, корректность которой доказывается. Показано, что на STAR-машине эта процедура выполняется за время O(hk), где h - число битов, которое требуется для кодирования длины максимального кратчайшего пути; к - число вершин, для которых вычисляются новые кратчайшие пути после добавления новой дуги к исходному графу. Приводятся результаты тестирования реализации алгоритма на графическом ускорителе.