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

The paper selects constructions used to represent a group of algorithms for undirected graphs given 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 analyzes the implementation on the STAR–machine of classical algorithms of Prim–Dijkstra, Kruskal, and Gabow, the method of finding paths with respect to a given spanning tree and its application to solving some tasks. Moreover, the paper proposes an improved version of implementing the Gabow algorithm for finding the smallest spanning tree with a degree constraint of a vertex on the STAR–machine.