An algorithm for the enumeration of spanning trees |
| |
Authors: | Pawel Winter |
| |
Affiliation: | (1) DIKU, Institute of Datalogy, University of Copenhagen, Sigurdsgade 41, DK-2200 Copenhagen N, Denmark;(2) Present address: Risø National Laboratory, Department of Electronics, DK-4000 Roskilde, Denmark |
| |
Abstract: | Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n2). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms. |
| |
Keywords: | Graph Theory Spanning Tree Enumeration Algorithm |
本文献已被 SpringerLink 等数据库收录! |
|