Algorithms for updating minimal spanning trees

Abstract

The problem of finding the minimal spanning tree on an undirected weighted graph has been investigated by many people and O(n2) algorithms are well known. P. M. Spira and A. Pan (Siam J. Computing 4 (1975), 375-380) present an O(n) algorithm for updating the minimal spanning tree if a new vertex is inserted into the graph. In this paper, we present another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex. Spira and Pan further show that the deletion of a vertex requires O(n2) steps. If all the vertices are considered, O(n3) steps may be used. The algorithm which we present here takes only O(n2) steps and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time. Similar results are obtained for the insertion and the deletion of an edge. © 1978.