Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure
The transitive closure (or reachability) problem in a directed graph consists in finding whether there is a path between any two vertices. In this paper, we first study the problem of parallelization of Italiano's algorithm for dynamic updating the transitive closure after inserting a new arc i...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут програмних систем НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/1443 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure / A. S. Nepomniaschaya // Пробл. програмув. — 2008. — N 2-3. — С. 97-102. — Бібліогр.: 9 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862725214795726848 |
|---|---|
| author | Nepomniaschaya, A.S. |
| author_facet | Nepomniaschaya, A.S. |
| citation_txt | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure / A. S. Nepomniaschaya // Пробл. програмув. — 2008. — N 2-3. — С. 97-102. — Бібліогр.: 9 назв. — англ. |
| collection | DSpace DC |
| description | The transitive closure (or reachability) problem in a directed graph consists in finding whether there is a path between any two vertices. In this paper, we first study the problem of parallelization of Italiano's algorithm for dynamic updating the transitive closure after inserting a new arc into the graph represented as a list of arcs. To this end, by means of the data structure first proposed in [9], Italiano's incremental algorithm is represented in a natural way on a model of an associative parallel processor with vertical processing (the STAR-machine). Associative version of Italiano's incremental algorithm is given as procedure InsertArc for the STAR-machine. We prove correctness of this procedure and evaluate its time complexity. We also compare implementations of Italiano's incremental algorithm and its associative version and present the main advantages of the associative version.
Проблема транзитивного замыкания (или достижимости) в ориентированном графе состоит в определении того, существует ли путь между любыми двумя вершинами. В данной статье впервые исследуется задача параллельной реализации алгоритма Итальяно для динамической обработки транзитивного замыкания после добавления к графу новой дуги для случая, когда граф задается в виде списка дуг. С этой целью с помощью структуры данных, впервые предложенной в работе [9], инкрементальный алгоритм Итальяно естественным образом представляется на модели ассоциативного параллельного процессора с вертикальной обработкой данных (STAR- машине). Ассоциативная версия инкрементального алгоритма Итальяно задается в виде процедуры InsertArc для STAR- машины. Доказывается корректность этой процедуры и оценивается ее временная сложность. Также проводится сравнение выполнения инкрементального алгоритма Итальяно и его ассоциативной версии и приводятся основные преимущества ассоциативной версии.
|
| first_indexed | 2025-12-07T18:51:16Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-1443 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | English |
| last_indexed | 2025-12-07T18:51:16Z |
| publishDate | 2008 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Nepomniaschaya, A.S. 2008-07-31T10:24:20Z 2008-07-31T10:24:20Z 2008 Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure / A. S. Nepomniaschaya // Пробл. програмув. — 2008. — N 2-3. — С. 97-102. — Бібліогр.: 9 назв. — англ. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1443 519.172 The transitive closure (or reachability) problem in a directed graph consists in finding whether there is a path between any two vertices. In this paper, we first study the problem of parallelization of Italiano's algorithm for dynamic updating the transitive closure after inserting a new arc into the graph represented as a list of arcs. To this end, by means of the data structure first proposed in [9], Italiano's incremental algorithm is represented in a natural way on a model of an associative parallel processor with vertical processing (the STAR-machine). Associative version of Italiano's incremental algorithm is given as procedure InsertArc for the STAR-machine. We prove correctness of this procedure and evaluate its time complexity. We also compare implementations of Italiano's incremental algorithm and its associative version and present the main advantages of the associative version. Проблема транзитивного замыкания (или достижимости) в ориентированном графе состоит в определении того, существует ли путь между любыми двумя вершинами. В данной статье впервые исследуется задача параллельной реализации алгоритма Итальяно для динамической обработки транзитивного замыкания после добавления к графу новой дуги для случая, когда граф задается в виде списка дуг. С этой целью с помощью структуры данных, впервые предложенной в работе [9], инкрементальный алгоритм Итальяно естественным образом представляется на модели ассоциативного параллельного процессора с вертикальной обработкой данных (STAR- машине). Ассоциативная версия инкрементального алгоритма Итальяно задается в виде процедуры InsertArc для STAR- машины. Доказывается корректность этой процедуры и оценивается ее временная сложность. Также проводится сравнение выполнения инкрементального алгоритма Итальяно и его ассоциативной версии и приводятся основные преимущества ассоциативной версии. en Інститут програмних систем НАН України Паралельне програмування Розподілені системи та мережі Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure Article published earlier |
| spellingShingle | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure Nepomniaschaya, A.S. Паралельне програмування Розподілені системи та мережі |
| title | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure |
| title_full | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure |
| title_fullStr | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure |
| title_full_unstemmed | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure |
| title_short | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure |
| title_sort | parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure |
| topic | Паралельне програмування Розподілені системи та мережі |
| topic_facet | Паралельне програмування Розподілені системи та мережі |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1443 |
| work_keys_str_mv | AT nepomniaschayaas parallelimplementationofitalianosincrementalalgorithmfordynamicupdatingthetransitiveclosure |