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

В работе строится эффективный ассоциативный параллельный алгоритм для динамической обработки дерева кратчайших путей после удаления одной дуги из ориентированного взвешенного графа. С этой целью вначале описывается используемая структура данных и ее построение, а также приводится STAR-машина, которая моделирует работу ассоциативных (контекстно-адресуемых) параллельных систем с простыми процессорными элементами и вертикальной обработкой информации. На этой модели ассоциативный параллельный алгоритм представляется в виде главной процедуры DeleteArcSPT, использующей группу вспомогательных процедур для выполнения его отдельных частей. Доказана корректность процедуры DeleteArcSPT и показано, что на STAR-машине она выполняется за время $O(hk)$, где $h$ — число битов, которое требуется для кодирования длины максимального кратчайшего пути, а $k$ — число вершин, для которых вычисляются новые кратчайшие пути после удаления одной дуги из исходного графа.