Efficient update of tree paths on associative systems with bit-parallel processing

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.