A space optimal algorithm for enumerating spanning trees of a connected graph


Ladislav Novak, Žarko Karadžić, Dragan M. Acketa




A simple space optimal algorithm is introduced for generating all the spanning trees of a connected graph $G$. The algorithm is based on a backtracking on the family $F$, which contains all the stars of $G$, with one single exception, sorted by non-decreasing cardinality. The efficiency of the algorithm is due to a local test, which gives the answer to the question: "Will the addition of a new edge a: to a cycle-free subset $S$ of edges of $G$ make the set $S\cup x$ contain a cycle of $G$?"