An optimal algorithm for scanning all spanning trees of undirected graphs

作     者：Shioura, A Tamura, A Uno, T 

作者机构：UNIV ELECTROCOMMUNDEPT COMP SCI & INFORMAT MATHCHOFUTOKYO 182JAPAN TOKYO INST TECHNOLDEPT SYST SCIMEGURO KUTOKYO 152JAPAN 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1997年第26卷第3期

页      面：678-692页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：optimal algorithm spanning trees undirected graphs 

摘      要：Let G be an undirected graph with V vertices and E edges. Many algorithms have been developed for enumerating all spanning trees in G. Most of the early algorithms use a technique called backtracking. Recently, several algorithms using a different technique have been proposed by Kapoor and Ramesh (1992), Matsui (1993), and Shioura and Tamura (1993). They find a new spanning tree by exchanging one edge of a current one. This technique has the merit of enabling us to compress the whole output of all spanning trees by outputting only relative changes of edges. Kapoor and Ramesh first proposed an O(N + V + E)-time algorithm by adopting such a compact output, where N is the number of spanning trees. Another algorithm with the same time complexity was constructed by Shioura and Tamura. These are optimal in the sense of time complexity but not in terms of space complexity because they take O(VE) space. We refine Shioura and Tamura s algorithm and decrease the space complexity from O(VE) to O(V + E) while preserving the time complexity. Therefore, our algorithm is optimal in the sense of both time and space complexities.