An algorithm for the enumeration of spanning trees
type: Item
instance of: scholarly article
title: An algorithm for the enumeration of spanning trees
zbMATH Open document ID: 0602.68054
DOI: 10.1007/BF01939361
author: Pawel Winter
published in: BIT
publication date: 1986-01-01T00:00:00Z
review text: 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 is \(O(n+m+nt)\) where n is the number of vertices, m the number of edges, and t the number of spannig trees in the graph. The worst-case space complexity of the algorithm is \(O(n^ 2)\). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3972205
zbMATH Keywords: spanning trees of an undirected graph
zbMATH Keywords: enumeration algorithm
zbMATH Keywords: contractions
zbMATH Keywords: time complexity
zbMATH Keywords: space complexity
MaRDI profile type: Publication
cites work: Q4091421
cites work: Gravitational instability and collapse of charged fluid shells
cites work: Finding All Spanning Trees of Directed and Undirected Graphs
cites work: Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
full work available at URL: https://doi.org/10.1007/bf01939361
OpenAlex ID: W2006156823
description: scientific article; zbMATH DE number 3972205