An Algorithm for Finding <i>K</i> Minimum Spanning Trees

Abstract

This paper presents an algorithm for finding K minimum spanning trees in an undirected graph. The required time is $O(Km + \min (n^2 ,m\log \log n))$ and the space is $O(K + m)$, where n is the number of vertices and m is the number of edges. The algorithm is based on three subroutines. The first two subroutines are used to obtain the second minimum spanning tree in $O(\min (n^2 ,m\alpha (m,n)))$ steps, where $\alpha (m,n)$ is Tarjan’s inverse of Ackermann’s function [12] which is very slowly growing. The third one obtains the kth minimum spanning tree in $O(m)$ steps when the jth minimum spanning trees for $j = 1,2, \cdots ,k - 1$ are given.