% file:         alltree12
% author:       Tomomi MATSUI 
% organization: Math. Eng. #2 Lab. (Tomomi MATSUI)
% email:        tomomi@misojiro.t.u-tokyo.ac.jp
% title:        A flexible algorithm for generating all the spanning trees in undirected graphs 
% keywords:     enumeration problem, spanning tree
% language:     English

@techreport   {alltree12,
    AUTHOR="T. Matsui",
    TITLE="A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs",
    YEAR=1996,
    INSTITUTION="University of Tokyo",
    TYPE="to appear in Algorithmica"}

\begin{abstract}
In this paper, we propose an algorithm 
   for generating all the spanning trees 
   in undirected graphs.
The algorithm requires O$(n+m+ \tau n)$ time
   where the given graph has $n$ vertices,  $m$ edges and
   $\tau$ spanning trees.
For outputting all the spanning trees explicitly,
   this time complexity is optimal.

Our algorithm follows a special rooted tree structure 
   on the skeleton graph of the spanning tree polytope.
The rule by which the rooted tree structure
   is traversed is irrelevant to the time complexity.
In this sense, our algorithm is flexible.

If we employ the depth-first search rule,
   we can save the memory requirement to O$(n+m)$.
A breadth-first implementation
  requires as much as O$(m+  \tau n)$ space,
  but when a parallel computer is available,
  this might have an advantage.
When a given graph is weighted,
   the best-first search rule provides 
   a ranking algorithm for the minimum spanning tree problem.
The ranking algorithm requires 
   O$(n+ m + \tau n)$ time
   and O$(m+ \tau n)$ space
   when we have a minimum spanning tree.
\end{abstract}