Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги
Запропоновано ефективну паралельну реалiзацiю алгоритму Рамалiнгама для динамiчного оброблення пiдграфа найкоротших шляхiв орiєнтованого графа пiсля додавання до нього однiєї дуги за допомогою моделi асоцiативних паралельних систем з вертикальним обробленням iнформацiї (STAR-машини). Асоцiативна вер...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84107 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84107 |
|---|---|
| record_format |
dspace |
| spelling |
Непомнящая, А.Ш. 2015-07-03T08:07:50Z 2015-07-03T08:07:50Z 2012 Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84107 519.172 Запропоновано ефективну паралельну реал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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги Асоцiативна версiя алгоритму Рамалiнгама для динамiчної оборобки пiдграфа найкоротших шляхiв пiсля додавання до графа нової дуги Associative version of the ramalingam algorithm for dynamic update of the shortest-path subgraph after insertion of a new edge to the graph Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| spellingShingle |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги Непомнящая, А.Ш. Кибернетика |
| title_short |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_full |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_fullStr |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_full_unstemmed |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_sort |
ассоциативная версия алгоритма рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| author |
Непомнящая, А.Ш. |
| author_facet |
Непомнящая, А.Ш. |
| topic |
Кибернетика |
| topic_facet |
Кибернетика |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Асоцiативна версiя алгоритму Рамалiнгама для динамiчної оборобки пiдграфа найкоротших шляхiв пiсля додавання до графа нової дуги Associative version of the ramalingam algorithm for dynamic update of the shortest-path subgraph after insertion of a new edge to the graph |
| description |
Запропоновано ефективну паралельну реал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.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84107 |
| fulltext |
|
| citation_txt |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. |
| work_keys_str_mv |
AT nepomnâŝaâaš associativnaâversiâalgoritmaramalingamadlâdinamičeskoiobrabotkipodgrafakratčaišihputeiposledobavleniâkgrafunovoidugi AT nepomnâŝaâaš asociativnaversiâalgoritmuramalingamadlâdinamičnoíoborobkipidgrafanaikorotšihšlâhivpislâdodavannâdografanovoídugi AT nepomnâŝaâaš associativeversionoftheramalingamalgorithmfordynamicupdateoftheshortestpathsubgraphafterinsertionofanewedgetothegraph |
| first_indexed |
2025-11-24T11:42:15Z |
| last_indexed |
2025-11-24T11:42:15Z |
| _version_ |
1850846066449055744 |