Two Algorithms for Generating Weighted Spanning Trees in Order

Abstract

Two algorithms for generating spanning trees of a connected graph in order of increasing weight are presented. The first generates the K smallest weight trees, where K can be specified in advance or during execution of the algorithm. The run time is $O(KE\alpha (E,V) + E\log E)$ and the space is $O(K + E)$; here V is the number of vertices, E is the number of edges, and $\alpha$ is Tarjan’s inverse of Ackermann’s function and is very slow-growing. The algorithm uses a minimum weight spanning tree as a “reference tree”, and exchanges edges to derive other trees. The second algorithm, a modification of the first, generates all spanning trees of the graph, in order. If N is the number of spanning trees, the time is $O(NE)$ and the space is $O(N+E)$.