Abstract

In this paper, we propose an efficient associative parallel algorithm for updating tree paths after every change in the underlying graph. Such a problem arises when we perform dynamic graph algorithms. To speed up time complexity of the algorithm, we use a new associative model called associative graph machine (AG-machine). It carries out bit-serial and fully parallel associative processing of matrices representing graphs as well as some basic operations on matrices. On the AG-machine, the algorithm is implemented as procedure TreePaths. We prove its correctness and evaluate time complexity.

File

nepomniaschaya_a_sh.pdf166.44 KB

Pages

71-83