Parallel implementation of italiano's incremental algorithm for dynamic updating the transitive closure

• Дата: 2008
• Автор: Nepomniaschaya, A.S.
• Формат: Стаття
• Мова: English
• Опубліковано: Інститут програмних систем НАН України 2008
• Теми: Паралельне програмування; Розподілені системи та мережі
• Онлайн доступ: http://dspace.nbuv.gov.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 назв. — англ.

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.