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...
Saved in:
| Date: | 2008 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут програмних систем НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/1443 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure / A. S. Nepomniaschaya // Пробл. програмув. — 2008. — N 2-3. — С. 97-102. — Бібліогр.: 9 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-1443 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure |
| spellingShingle |
Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure Nepomniaschaya, A.S. Паралельне програмування Розподілені системи та мережі |
| title_short |
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_sort |
parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure |
| author |
Nepomniaschaya, A.S. |
| author_facet |
Nepomniaschaya, A.S. |
| topic |
Паралельне програмування Розподілені системи та мережі |
| topic_facet |
Паралельне програмування Розподілені системи та мережі |
| publishDate |
2008 |
| language |
English |
| publisher |
Інститут програмних систем НАН України |
| format |
Article |
| 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- машины. Доказывается корректность этой процедуры и оценивается ее временная сложность. Также проводится сравнение выполнения инкрементального алгоритма Итальяно и его ассоциативной версии и приводятся основные преимущества ассоциативной версии.
|
| issn |
1727-4907 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/1443 |
| 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 назв. — англ. |
| work_keys_str_mv |
AT nepomniaschayaas parallelimplementationofitalianosincrementalalgorithmfordynamicupdatingthetransitiveclosure |
| first_indexed |
2025-12-07T18:51:16Z |
| last_indexed |
2025-12-07T18:51:16Z |
| _version_ |
1850876600207278080 |