ASSOCIATIVE PARALLEL ALGORITHM FOR DYNAMIC UPDATE OF A MINIMUM SPANNING TREE AFTER ADDITION OF A NEW NODE TO A GRAPH

摘要

This paper proposes a new associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node with all its incident edges to a graph. This algorithm is represented as the InsertVert procedure implemented on a model of an associative parallel system of the SIMD type with vertical processing (a STAR machine). The correctness of the procedure is proved and its time complexity is estimated.