Заседание семинара "Математическое обеспечение высокопроизводительных вычислительных систем" 26.04.2017 в 15-00. "Ассоциативная версия инкрементального алгоритма Рамалингама для динамической обработки кратчайших путей между любыми парами вершин ориентированного графа", Непомнящая А.Ш.

В работе строится ассоциативная версия последовательного алгоритма Рамалингама для динамической обработки кратчайших путей между любыми парами вершин ориентированного взвешенного графа после добавления новой дуги. С этой целью используется модель ассоциативных (или контекстно-адресуемых) параллельных систем  с вертикальной обработкой информации (STAR-машина). После краткого введения и краткого описания STAR- машины приводится упрощенная версия инкрементального алгоритма Рамалингама для динамической обработки подграфа кратчайших путей с одним стоком. Отметим, что упрощенная версия этого алгоритма Рамалингама будет использоваться для динамической обработки кратчайших путей между любыми парами вершин графа после добавления новой дуги. Упрощенная версия алгоритма Рамалингама находит те вершины подграфа, кратчайший путь от которых до стока изменяется  после добавления новой дуги. Такие вершины называются аффектными. Новые кратчайшие пути до стока будут вычисляться только для аффектных вершин. Упрощенная версия инкрементального алгоритма Рамалингама для обработки подграфа кратчайших путей с одним стоком представляется в виде функции InsertUpdate(G,(i,j),z). Эта функция вычисляет множество всех аффектных вершин и новые пути от них до стока z. Алгоритм Рамалингама для динамической обработки кратчайших путей между любыми парами вершин после добавления новой дуги задается в виде процедуры InsertEdge. В этой процедуре вначале к графу добавляется новая дуга. Затем с помощью функции InsertUpdate  вычисляется множество аффектных стоков. Затем для каждого аффектного стока вычисляется функция InsertUpdate. Чтобы представить .этот алгоритм на STAR-машине, вначале приводится структура данных. Затем приводится ассоциативный параллельный алгоритм для выполнения функции InsertUpdate. После этого приводится реализация на STAR-машине процедуры InsertEdge. Доказана корректность этой процедуры и оценена ее сложность. Приведены основные достоинства ассоциативной версии инкрементального  алгоритма Рамалингама для динамической обработки кратчайших путей между любыми парами вершин ориентированного графа.