Effective representation of algorithm for finding a minimal spanning tree of a graph in associative parallel processor

In this paper we analyze two procedures for finding a minimal spanning tree of a graph for an abstract associative STAR-machine with bit-serial processing. These procedures are based on the Prim-Dijkstra algorithm and use different graph representations. We prove their correctness, evaluate their complexity and compare them. In addition, we compare two procedures for the same graph representation.