A parallel algorithm for k-minimum spanning trees

A parallel algorithm to find k, 2⩽k⩽n^n-2, spanning trees from a connected, weighted and undirected graph C(V, E, W) in the order of increasing weight is presented. It runs in O(T(n)+klogn) time with O(n²/log n) processors on a CREW PRAM, where n=|V|, m=|E| and T(n), O(log n)⩽T(n)⩽O(log² n), is the time of the fastest parallel algorithms to find a minimum spanning tree of G on a CREW PRAM with no more than O(n² /log n) processors. Since T(n)=O(log² n) for the time being, this result shows that to find k minimum spanning trees can be done in the same time bound as to find just one when k⩽O(log n) on a CREW PRAM