%T Optimal Parallel and Sequential Algorithms for the Vertex Updating Problem of a Minimum Spanning Tree
%A Donald B. Johnson
%A Panagiotis Metaxas
%R Technical Report PCS-TR91-159
%I Dartmouth College, Computer Science
%C Hanover, NH
%D  1991
%U http://www.cs.dartmouth.edu/reports/TR91-159.pdf
%X
 	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.