An efficient parallel algorithm for updating minimum spanning trees

AbstractA new parallel algorithm for updating the minimum spanning tree of an n-vertex graph following the addition of a new vertex is presented. The algorithm runs in O(log n) time using O(n) processors on a concurrent-read-exclusive-write parallel random access machine. The algorithm is superior to previous algorithms on this model, that either obtain O(log n) time performance using O(n2) processors, or employ O(n) processors but have a time complexity of O(log2n)