Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / Непомнящая А. Ш. (2012)
Ukrainian

web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0000232482
  Cybernetics and Systems Analysis      А - 2019  /     Issue (2012, Т. 48, № 3)

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

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.

Бібліографічний опис:
Непомнящая А. Ш.  Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги. Кибернетика и системный анализ. 2012. Т. 48, № 3. С. 45-57. URL: http://jnas.nbuv.gov.ua/article/UJRN-0000232482

English  Cybernetics and Systems Analysis   /     Issue (2012, 48 (3))

translit Transliteration

Nepomnjashchaja A. Sh.
Assotsiativnaja versija algoritma Ramalingama dlja dinamicheskoj obrabotki podgrafa kratchajshikh putej posle dobavlenija k grafu novoj dugi

Cite:
Nepomnjashchaja, A. Sh. (2012). Assotsiativnaja versija algoritma Ramalingama dlja dinamicheskoj obrabotki podgrafa kratchajshikh putej posle dobavlenija k grafu novoj dugi. Cybernetics and Systems Analysis, 48 (3), 45-57 http://jnas.nbuv.gov.ua/article/UJRN-0000232482 [In Russian].

 

Institute of Information Technologies of VNLU

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Ukraine, 03039, Kyiv, Holosiivskyi Ave, 3, room 209