Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги
Запропоновано ефективну паралельну реалiзацiю алгоритму Рамалiнгама для динамiчного оброблення пiдграфа найкоротших шляхiв орiєнтованого графа пiсля додавання до нього однiєї дуги за допомогою моделi асоцiативних паралельних систем з вертикальним обробленням iнформацiї (STAR-машини). Асоцiативна вер...
Збережено в:
| Видавець: | Інститут кібернетики ім. В.М. Глушкова НАН України |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84107 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Цитувати: | Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. |
Репозиторії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84107 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841072015-07-04T03:01:22Z Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги Непомнящая, А.Ш. Кибернетика Запропоновано ефективну паралельну реал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. 2012 Article Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84107 519.172 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Непомнящая, А.Ш. Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги Кибернетика и системный анализ |
| description |
Запропоновано ефективну паралельну реалiзацiю алгоритму Рамалiнгама для динамiчного оброблення пiдграфа найкоротших шляхiв орiєнтованого графа пiсля додавання до нього однiєї дуги за допомогою моделi асоцiативних паралельних систем з вертикальним обробленням iнформацiї (STAR-машини). Асоцiативна версiя цього алгоритму описана у виглядi процедури InsertNewArc, коректнiсть якої доводиться. Наведено основні переваги асоцiативної версiї iнкрементального алгоритму Рамалiнгама. |
| format |
Article |
| author |
Непомнящая, А.Ш. |
| author_facet |
Непомнящая, А.Ш. |
| author_sort |
Непомнящая, А.Ш. |
| title |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_short |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_full |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_fullStr |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_full_unstemmed |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| title_sort |
ассоциативная версия алгоритма рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84107 |
| citation_txt |
Ассоциативная версия алгоритма Рамалингама для динамической обработки подграфа кратчайших путей после добавления к графу новой дуги / А.Ш. Непомнящая // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 45-57. — Бібліогр.: 14 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT nepomnâŝaâaš associativnaâversiâalgoritmaramalingamadlâdinamičeskojobrabotkipodgrafakratčajšihputejposledobavleniâkgrafunovojdugi |
| first_indexed |
2023-10-18T19:28:13Z |
| last_indexed |
2023-10-18T19:28:13Z |
| _version_ |
1796147044780343296 |