Constructions used in associative parallel algorithms for undirected graphs. Part 2

This paper selects constructions used in a group of algorithms for undirected graphs represented as a list of edges and their weights on a model of associative (content addressable) parallel systems with vertical processing (the STAR-machine). To this end, the paper first analyzes the implementation of the Prim-Dijkstra algorithm on the STAR-machine for finding an MST along with the method of finding the tree paths with respect to a given spanning tree. Then the paper considers the implementation on the STAR-machine of the dynamic graph algorithms for updating an MST. This group includes associative parallel algorithms for the dynamic edge update of an MST and for the dynamic reconstruction of an MST after deleting or after inserting a vertex along with its incident edges.