An Algorithm for Finding K Minimum Spanning Trees

This paper presents an algorithm for finding K minimum spanning trees in an undirected graph. The required time is O(Km + min (n² ,mlog 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² ,mα (m,n))) steps, where α (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, ⋯ ,k - 1 are given.