Во многих приложениях графы изменяются в результате добавления или удаления ребер или вершин. Цель динамического алгоритма – эффективно обработать динамические изменения в нем вместо перевычисления графа целиком после каждого локального изменения. В работе строится эффективный ассоциативный алгоритм для динамической обработки дерева кратчайших путей после удаления одной дуги из ориентированного взвешенного графа. С этой целью мы используем STAR-машину, которая моделирует работу ассоциативных (контекстно-адресуемых) параллельных систем с простыми однобитовыми процессорными элементами и последовательно-поразрядной (вертикальной) обработкой информации. Вначале приводится STAR-машина и группа базовых процедур, которые будут использоваться в статье. Затем мы описываем основные определения и структуру данных, позволяющую выполнять параллельную обработку данных по содержимому памяти. Ассоциативный алгоритм представляется на STAR-машине в виде главной процедуры DeleteArcSPT, использующей группу вспомогательных процедур. С помощью вспомогательных процедур описываются отдельные части ассоциативного алгоритма для динамической обработки дерева кратчайших путей после удаления из графа одной дуги.
В работе доказана корректность процедуры DeleteArcSPT и оценена ее временная сложность. Мы показали, что на STAR-машине эта процедура выполняется за время O(hk), где h – это число битов, которое требуется для кодирования длины максимального кратчайшего пути, а k – это число вершин, для которых вычисляются новые кратчайшие пути после удаления одной дуги из исходного графа.
| Full text file: | Anna_Nepom.pdf |