Listing all the minimum spanning trees in an undirected graph

Abstract

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.

Keywords:

• minimum spanning tree
• enumeration algorithm

2000 AMS Classifications :

• 05C05
• 05C30
• 68W05

Acknowledgements

The authors are grateful to two anonymous referees and and a Editor for their constructive criticisms and suggestions. Numerous comments from Professor Kazuo Ouchi were substantial in improving the quality of English in this paper, for which we express deep appreciation.