Efficiently Enumerating Spanning Trees of <i>k</i> -Trees

A spanning tree T of a connected graph G is an acyclic subgraph of G that connects all vertices of G with the minimum number of edges. Spanning tree enumeration is the problem of finding all distinct spanning trees of G and is a well-studied problem in graph theory with applications in various fields. In this paper, we propose an algorithm for enumerating spanning trees of k-trees that runs in [Formula: see text] time and takes [Formula: see text] space for a k-tree G having n vertices, m edges, and [Formula: see text] spanning trees. This is a substantial improvement in time complexity without increasing the space cost over the best spanning tree enumeration algorithm for general graphs which takes [Formula: see text] time and also requires [Formula: see text] space.