Affiliations: Institute of Computational Mathematics and
Mathematical Geophysics, Siberian Division of Russian Academy of Sciences, pr.
Lavrentieva, 6, Novosibirsk, 630090, Russia. anep@ssd.sscc.ru
Note: [] Address for correspondence: Laboratory of parallel algorithms
and structures, pr. Lavrentieva, 6, Novosibirsk, 630090, Russia
Abstract: We propose a simple data structure for an efficient implementation
of the Italiano algorithms for the dynamic updating of the transitive closure
of a directed graph represented as adjacency matrix on a model of associative
(or content addressable) parallel processors with vertical processing (the
STAR–machine). Associative versions of the Italiano algorithms are
represented as procedures DeleteArc1 and InsertArc1. We prove the correctness
of these procedures and evaluate their time and space complexity. We also
present the main advantages of associative versions of the Italiano
algorithms.
Keywords: Directed graph, spanning tree, adjacency matrix, transitive closure of a directed graph, incremental algorithm, decremental algorithm, associative parallel processor, access data by contents
