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

• Published in: Кибернетика и системный анализ
• Date: 2012
• Main Author: Непомнящая, А.Ш.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
• Subjects: Кибернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/84107
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос.

Запропоновано ефективну паралельну реалiзацiю алгоритму Рамалiнгама для динамiчного оброблення пiдграфа найкоротших шляхiв орiєнтованого графа пiсля додавання до нього однiєї дуги за допомогою моделi асоцiативних паралельних систем з вертикальним обробленням iнформацiї (STAR-машини). Асоцiативна версiя цього алгоритму описана у виглядi процедури InsertNewArc, коректнiсть якої доводиться. Наведено основні переваги асоцiативної версiї iнкрементального алгоритму Рамалiнгама. In this paper, we propose an efficient parallel implementation of the Ramalingam algorithm for the dynamic update of the single-sink shortest path subgraph of a directed graph after adding an edge with the use of the model of associative (content addressable) parallel systems with vertical processing (STAR-machine). An associative version of this algorithm is described as the InsertNewArc procedure, whose correctness is proved. We also present the main advantages of the associative version of the Ramalingam incremental algorithm.