A new technique for updating tree paths on associative parallel processors

In this paper we describe in detail a new technique for updating tree paths on a model of associative parallel systems with vertical data processing (the STAR-machine). It includes a new associative parallel algorithm for finding an MST along with the matrix of tree paths and a new associative parallel algorithm for updating tree paths after every change in the underlying graph. We prove correctness of the corresponding procedures and evaluate time complexity. Moreover, we compare two techniques for updating tree paths on the STAR-machine and the CREW PRAM machine.