Listing all the minimum spanning trees in an undirected graph

Abstract

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 2 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 treeenumeration algorithm 2000 AMS Classifications : 05C0505C3068W05 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.