An adaptive and cost-optimal parallel algorithm for minimum spanning trees (Q1060018)

A parallel algorithm is described for computing the minimum spanning tree of an undirected, connected and weighted graph with n vertices. We assume a shared-memory single-instruction-stream, multiple-data-stream model of computation which does not allow read or write conflicts. The algorithm is adaptive in the sense that it uses \(n^{1-e}\) processors and runs in \(O(n^{1+e})\) time where e lies between 0 and 1 and depends on the number of available processors. In view of the obvious \(\Omega (n^ 2)\) lower bound on the number of operations required to compute a minimum spanning tree, the algorithm is also cost-optimal.