Optimal Parallel and Sequential Algorithms for the Vertex Updating Problem of a Minimum Spanning Tree

We present a set of rules that can be used to give optimal solutions to the vertex updating problem for a minimum spanning tree: Update a given MST when a new vertex z is introducted, along with weighted edges that connect z with the vertices of the graph. These rules lead to simple parallel algorithms that run in O(lg n) parallel time using n/lg n EREW PRAMs. They can also be used to derive simple linear-time sequential algorithms for the same problem. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem