Прикладная дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2019, номер 46, страницы 58–71 (Mi pdm684)  

Математические основы информатики и программирования

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

А. Ш. Непомнящая, Т. В. Снытникова

Институт вычислительной математики и математической геофизики СО РАН, г. Новосибирск, Россия

Аннотация: Строится ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги к ориентированному взвешенному графу. Кратко описывается STAR-машина, которая моделирует работу ассоциативных (контекстно-адресуемых) параллельных систем с простейшими процессорными элементами и вертикальной обработкой информации. Описывается используемая структура данных и её свойства. Ассоциативный параллельный алгоритм представляется в виде процедуры InsertArcSPT, корректность которой доказывается. Показано, что на STAR-машине эта процедура выполняется за время O$(hk)$, где $h$ — число битов, которое требуется для кодирования длины максимального кратчайшего пути; $k$ — число вершин, для которых вычисляются новые кратчайшие пути после добавления новой дуги к исходному графу. Приводятся результаты тестирования реализации алгоритма на графическом ускорителе.

Ключевые слова: ориентированный взвешенный граф, матрица смежности, инкрементальный алгоритм, аффектная вершина, вертикальная обработка данных, ассоциативный параллельный процессор.

DOI: https://doi.org/10.17223/20710410/46/5

Полный текст: PDF файл (783 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 591.68

Образец цитирования: А. Ш. Непомнящая, Т. В. Снытникова, “Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги”, ПДМ, 2019, № 46, 58–71

Цитирование в формате AMSBIB
\RBibitem{NepSny19}
\by А.~Ш.~Непомнящая, Т.~В.~Снытникова
\paper Ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после добавления новой дуги
\jour ПДМ
\yr 2019
\issue 46
\pages 58--71
\mathnet{http://mi.mathnet.ru/pdm684}
\crossref{https://doi.org/10.17223/20710410/46/5}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm684
  • http://mi.mathnet.ru/rus/pdm/y2019/i4/p58

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:61
    Полный текст:20
    Литература:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2022