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

інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0000232482
  Кибернетика и системный анализ      А - 2019  /     Випуск (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].

 

Інститут інформаційних технологій НБУВ

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна