(C) Springer Verlag, Lecture Notes on Computer Science

A New Approach for Speeding Up
Enumeration Algorithms
Takeaki UNO
Dept. Industrial Engineering and Management, Tokyo Institute of Technology,

2-12-1 Oh-okayama, Meguro-ku, Tokyo 152, Japan. uno@me.titech.ac.jp

Abstract: We propose a new approach for speeding up enumeration algorithms. The approach does not relies on data structures deeply, but utilizes someanalysis of its computation time. The enumeration algorithms for directed spanning trees, matroid bases, and some bipartite matching problems are speeded
up by this approach. For a given graph G = (V, E), the time complexity of thealgorithm for directed spanning tree is O(log2 |V |) per a directed spanning tree.
For a given matroid M, the algorithm for matroid bases runs in O(T /n) time
per a base. Here n denotes the rank of M, and T denotes the computation time
to obtain elementary circuits. Enumeration algorithms for matching problems
spend O(|V |) time per a matching.

1

Introduction

For many graph and geometry objects, enumeration algorithms have been developed. Speeding up is one of important and interesting parts of the studies on
enumeration algorithms. There are many algorithms and their improvements,
especially for spanning trees and paths [1, 2, 3, 4], although neither generalized
technique nor framework is proposed for these improvements. Almost all fastenumeration algorithms are improved by speeding up their iterations with somedata structures. Hence if we can not speed up iterations, we may obtain no fastalgorithm.
In this paper, we propose a new approach “trimming and balancing” forspeeding up enumeration algorithms. Our approach is not based on data structures, hence we can apply it to many enumeration algorithms which have notbeen improved in the existing studies. Our approach adds two new phases toan enumeration algorithm, which are called the trimming phase and the balancing phase. By adding these, an iteration of a modiﬁed algorithm may takemuch computation time than original one, but the total time complexity of themodiﬁed algorithm is often considerably smaller than the original. Some ouralgorithms with the worst case time complexities of an iteration larger than theoriginal one often attain a better upper bound of the time complexity than theoriginal. The time complexity of a trimming and balancing algorithm is not soeasy to analyze. We use a technique to analyze time complexities. In the next

section, we show the framework of the approach and the technique of our analysis. We also show a trimming and balancing algorithm for the enumeration
problem of directed spanning trees.

2

Framework of Trimming and Balancing

At the beginning of this section, we explain the idea of the trimming phaseand balancing phase. To explain it, we use a binary partition algorithm for theenumeration problem of directed spanning trees whose root is a speciﬁed vertex r. The algorithm is proposed by H.N.Gabow and E.W.Myers [1] in 1978.
A directed spanning tree ( denoted by DST ) is a spanning tree of a digraphsatisfying that no its arc shares its head with the other. The algorithm inputs a
digraph, and chooses an not “unnecessary” arc a∗ (which is called a partitioning arc ). An unnecessary arc is an arc included in all DSTs or no DST. The
algorithm divides the problem into two subproblems of enumerating all DSTs
including a∗ , and all those not including a∗ . These subproblems can be solved
recursively with the graph obtained by removing all the arcs sharing their heads
with a∗ , and that obtained by removing a∗ . If there is only one DST, then all
the arcs are unnecessary. Hence the algorithm stops. The algorithm is known
to take O(|A|) time per an iteration, and per an outputted DST. Here we show
the details of the algorithm.
ALGORITHM: Enum DST (G = (V, A) )Step 1: Find a partitioning arc a∗ . If there are only unnecessary arcs,
then output the unique DST and stop.
Step 2: Remove all arcs sharing their heads with a∗ , and call Enum DST(G).
Step 3: Remove a∗ from G, and call Enum DST (G) recursively.
The trimming phase removes unnecessary parts from the input. In this algorithm, unnecessary arcs can be removed or contracted, since removals andcontractions of these arcs eﬀect no change to the original problem. These removals and contractions reduce the size of the input, thus the reduced input
includes many outputs for its size. For example, as we show in the later section,a digraph G = (V, A) including no unnecessary arc ( “unnecessary” is characterized in the just above ) contains Ω(|A|) DSTs. By the trimming phase, thecomputation time of an iteration will be not so large for the number of outputs,
hence the total computation time per an output will be small.
The trimming phase decreases the computation time but does not always
decrease the computation time of the worst case. Suppose that the algorithm
inputs a digraph shown in the Figure 1. As we can see, no arc is unnecessary.
Now we suppose that the algorithm choose the arc a as a partitioning arc. Since
only one DST includes a, one of the subproblem terminates immediately. To
construct the other subproblem, a is removed. By the trimming algorithm, thearc sharing its head with a is contracted. The shape of the obtained graph issame as the original. If all the subproblems occurring in the algorithm choose

arbFig. 1. A digraph for enumeration problem of DSTs

the end-arc as a partitioning arc like the above, the total computation time willbe O(|A| +(|A|−2)+(|A|− 4)+... +4). One of the subproblems of them outputs
a DST, hence the total computation time is O(|A|) per a DST.
Why the worst case running time does not decrease? The answer is that thechoosing rule of partitioning arcs is bad. To reduce the time complexity, we haveto make a good rule. The balancing phase is added for this reason. It chooses
a partitioning arc such that both generated subproblems output not so few
DSTs. The subproblems have not so many arcs for the number of outputs after
the trimming phase, since we have a lower bound of the number of DSTs for its
input size. Thus, if the input includes few DSTs like the above example, then the
inputs of both subproblems will be small. Moreover, the depth of the recursion
is small in this case, hence the total time complexity will be reduced. As weshow in the later section, there is an arc such that both generated subproblems
have at least |A|/4 arcs after the trimming phase. In the ﬁgure 1, the arc b issuch an arc. The both generated subproblems by b have about |A|/2 arcs after
the trimming phase. The shapes of the obtained graphs are also like the ﬁgured
graph. Hence, by choosing partitioning arcs similarly, the depth of the recursionis O(log |A|). The total time complexity is also reduced.
The trimming and balancing approach decreases the time complexities ofenumeration algorithms, but it is not easy to estimate a good upper bound of
those time complexities. There are some diﬃcult algorithms to analyze theirtime complexities. In this paper, we also show a technique for analyzing thetime complexities of enumeration algorithms. We explain it in the following.
Before explaining our analysis, we introduce a virtual tree called an enumeration tree of an enumeration algorithm, which expresses the structure of
the recursive calls. For a given enumeration algorithm and its input, let V be avertex set whose elements correspond to all recursive calls occurring in the algorithm. We consider an edge set E on V × V such that each whose edge connects
two vertices if and only if a recursive call corresponding to one of the vertices
occurs in the other. Since the structure of a recursive algorithm contains no circulation, the graph T = (V, E) forms a tree. This tree is called an enumeration
tree of the algorithm. The root vertex of the tree corresponds to the start of
the algorithm. To analyze enumeration algorithms, we show some properties ofenumeration trees which satisfy for any input.
To analyze the time complexity of an enumeration algorithm, we consider thefollowing distribution rule on the enumeration tree. Let T be an enumeration
tree, and D(x) be the number of descendants of a vertex x of T . Supposethat T (x) is an upper bound of the time complexity of an iteration x. We

also suppose that T̂ is an upper bound of maxx∈T {T (x)/D(x)}. Our analysis
uses a parameter T ∗ . The distribution is done from a vertex to its children
in the top-down manner. For a vertex x of the enumeration tree, let Tp (x)be the computation time distributed by the parent of x to x. We distribute
Tp (x) + T (x) − T ∗ of the computation time to its children such that each childreceives the computation time proportional to the number of its descendants.
We distribute the computation time of each child recursively.
By this distribution rule, some vertices may receive much computation time.
Thus we deﬁne excess vertices for a speciﬁed positive constant α > 1, and stop
the distribution on the excess vertices. A vertex x is called excess if Tp (x) +T (x) > αT̂ D(x). The children of an excess vertex receive no computation timefrom their parent. The distribution rule is also applied to the descendants ofexcess vertices. By this new rule, Tp (x) is bounded by αT̂ D(x) for any vertex x,
since the computation time distributed from a parent to its child is proportional
to the number of descendants of the child.
After the distribution, no vertex except excess vertices has more than O(T̂ +T ∗ ) on it. Next, we distribute the computation time on each excess vertex x to allits descendants uniformly. Since the excess time Tp (x)+T (x)−T ∗ is bounded by(α + 1)T̂ D(x), each descendant receives at most (α + 1)T̂ time from an excess
ancestor. Let X ∗ be an upper bound of the maximum number of the excess
vertices on a path from the root to a leaf. By using X ∗ we obtain an upperbound O(T ∗ + T̂ X ∗ ) of the time complexity per an iteration. From these facts,
we obtain the following theorem.
Theorem 1. An enumeration algorithm terminates in O(T ∗ + T̂ X ∗ ) time peran iteration.
Our analysis requires T̂ and X ∗ . To obtain a good upper bound of the timecomplexity, we have to set X ∗ and T̂ to suﬃciently good values. As a candidateof T̂ , we can utilize maxx∈T {T (x)/D̄(x)} where D̄(x) is a lower bound of D(x).
In the enumeration tree, it is hard to identify excess vertices, although we canobtain an eﬃcient upper bound X ∗ . Let x and y be excess vertices such that yis an ancestor of x and no other excess vertex is in the path Pyx from y to x in
the enumeration tree. Note that Pyx has at least one internal vertex.
Lemma 2. At least one vertex w of Pyx \ y satisfies the condition that T (w) isαlarger than the sum of α+1
T (u) over all children u of w.
Proof. If Pyx \ y includes no such vertex, then all vertices w of Pyx \ y satisfy thecondition that Tp (w) ≤ αT̂ D(w). It contradicts to the assumption of the statement. We prove it by induction. Any child of y satisﬁes the condition since y is anexcess vertex. Suppose that a vertex w of Pyx \ y holds Tp (w ) ≤ αT (w ), wherew  is the parent of w. Then Tp (w) ≤ (α+1)T (w )D(w)/D(w ). From the assumpαtion, T (w ) is not greater than the sum of α+1
T̂ D(u) over all children u of w  .

16

= 1.2

12

12

3

2

1

6

8

6

4

5

2

3

7

4

2

1

Fig. 2. The enumeration tree and computation time on each vertex: The vertices
satisfying the condition of Lemma 1 are drawn by emphasized circles, and all leaves
are drawn by rectangles. In this tree, we can set T̂ to 7, and X ∗ to 2.
αT̂ D(w ).
Since the sum of D(u) is not greater than D(w ), we have T (w ) ≤ α+1Therefore we have Tp (w) ≤ α(α+1)
α+1 T̂ D(w )D(w)/D(w ) = αT̂ D(w).
∗From this lemma, we can obtain X by estimating an upper bound of thenumber of vertices satisfying this condition in any path from the root to a leaf.
Similarly, we can obtain the following corollary.

Corollary 1 If T̂ = maxx∈T {T (x)/D̄(x)}, a vertex w of Pyx \ y satisfies thatαD̄(w) is larger than the sum of α+1
D̄(u) over all children u of w.
These conditions can be easily checked, and are often suﬃcient to analyze.
In the following sections, we describe one of them, that for DSTs. To see thealgorithms for perfect matchings, refer [5].

3Enumerating Directed Spanning Trees

In this section, we consider an enumeration algorithm for DSTs. Our algorithm
is obtained by adding a trimming phase and a balancing phase to the algorithm
explained in the previous section. We describe these algorithms in the following
sections.

3.1

A Trimming Algorithm

Our trimming algorithm removes unnecessary parts of input. Firstly, the algorithm removes all multiple arcs since at most one of multiple arcs can be
included in a DST. Next we see characterizations for unnecessary arcs which
are included in all DSTs or no DST.
Property 1 For an arc (u, v), there is a DST including it if and only if there
is a simple dipath from r to u not including v.
Property 2 For an arc (u, v), there is a DST not including it if and only ifthere is a simple dipath from r to v not including (u, v).

1

2

10

3

4

7

11

b
a

5

8

6

9

Fig. 3. Back arc a is included in a DST since i(h(6, 6)) = 2. Back arc b is included in
no DST since i(h(7, 7)) = 3 and i(h(8, 8)) = 7.

From Property 2, if all arcs not satisfying the former condition are removed,
then an arc is not included in a DST if and only if it shares its head with theother arc. Let T be a depth-ﬁrst search tree of G with the root r. For a non-backarc a of T, the dipath from r to the tail of a in T does not include the head ofa. Thus the former condition holds for any non-back arc. In the following, weshow a way for checking the condition for back arcs.
Let us put indices i(v) to all vertices v in the order of visiting of the depthﬁrst search. We denote the unique path in T from a vertex u to its descendantv by Puv . For an index i, vertices v and u, we call a dipath from u to v an
i-bypass if all its internal vertices have indices larger than or equal to i. For avertex v and an index i ≤ i(v), let h(v, i) be the minimum index vertex among
vertices satisfying that there are some i-bypasses from the vertices to v. Since
any dipath to v from a vertex with an index smaller than v includes a common
ancestor of them, h(v, i) is an ancestor of v. Note that an ancestor has an index
smaller than any its descendant. By using these notations, we state the following
lemmas ( see Figure 3 ).
Lemma 3. For a back arc (u, v), there is a dipath from r to u not including v
if and only if i(h(w, i(w))) < i(v) holds for a vertex w in Pvu \ v.
Proof. The “if” part of the lemma is obviously. Suppose that there is a simple
dipath P from r to u not including v. Then P includes some vertices of Pvu \ v.
Let w be the ﬁrst vertex of them to appear in the path. The subpath of P fromr to w includes some ancestors of v. Let w  be the last vertex of them to appear
in the subpath. Note that no vertex of Pw w is an internal vertex of the subpath
from w  to w of P. Moreover, the subpath includes no vertex u with i(u) < i(v)since any path from u to v includes some common ancestors of u and v, since
T is a depth-ﬁrst search tree. It contradicts the choosing way of w  .
From this lemma, we can identify unnecessary arcs by using h. Our algorithm
ﬁrstly obtains h(v, i(v)) for the vertex v with i(v) = n. In each iteration, we
decrease i one by one, and obtain h(v, i) from h(v, i + 1) for all v with i(v) ≥ i.
The updating method of h is based on the following properties.

Lemma 4. Suppose that a vertex u has the index i − 1.
(1) h(u, i − 1) is the minimum index vertex among all v and h(v, i) satisfyingthat there are arcs (v, u).
(2) If h(v, i) = h(v, i − 1) holds for a vertex v, then v is a descendant of u andholds h(v, i − 1) = h(u, i − 1).
Proof. (1) Let P be an i − 1-bypass from h(u, i − 1) to u. If P is not an arc
from h(u, i − 1) to u, the vertex v next to u satisﬁes h(v, i) = h(u, i − 1). Thus
the condition holds. (2) If h(v, i − 1) = h(v, i), u is included in any i − 1-bypass
from h(v, i − 1) to v. Hence h(v, i − 1) = h(u, i − 1). Since (a) a dipath from u
to a vertex with an index larger than i − 1 includes a common ancestor of them,and (b) any ancestor of u has an index smaller than i − 1, v is a descendant ofu. Therefore h(v, i − 1) = h(v, i) holds only for descendants of u.
From the lemma, we can see that i(h(v, j)) ≤ i(h(v, i)) for any j < i.
Lemma 5. Let u be a vertex satisfying that i(u) > i, and v be a descendant ofu. If we have h(u, i) = h(v, i), then h(u, j) = h(v, j) holds for any j < i.
Proof. Since u is an ancestor of v, i(h(u, j)) ≥ i(h(v, j)) holds for any j. Supposethat an index j satisﬁes i(h(u, j)) > i(h(v, j)). We assume that j is the maximum
index among indices satisfying the condition. From this assumption, there is a
j-bypass from h(v, j) to v not including u. Note that the bypass includes thevertex v whose index is j. Since T is a depth-ﬁrst search tree, any dipath fromv to v includes some common ancestors of v and v . These ancestors are also
ancestors of u, thus we can obtain a j-bypass from h(v, j) to u by merging the
j-bypass from h(v, j) to v and Pv u . It contradicts the assumption.
From the lemma, if we have h(u, i) = h(v, i) for u and its child v, the equation
holds for all j < i. Hence, in the graph obtained by contracting u and v, h ispreserved. Thus we contract them if such a vertex and a child exist. For a vertex
u, if a descendant v of u satisﬁes that i(h(v, i(u)+1)) > i(h(v, i(u))), the child v
of u included in the dipath from u to v satisﬁes the condition i(h(v , i(u) + 1)) >i(h(u, i(u))). Hence v and u satisfy that i(h(v , i(u))) = i(h(u, i(u))). Therefore,in each iteration with the index i, we ﬁnd the child v of the vertex u with i(u) = i
which maximizes i(h(v , i)) among all children of u. If v satisﬁes i(h(v , i)) <i(h(u, i)), all descendants v of u satisﬁes i(h(v, i)) < i(h(u, i)). Otherwise, wehave that h(v , i) = h(u, i), hence we contract u and v . We do this operation
until there is no child v satisfying i(h(v, i)) = i(h(u, i)). After contracting allthese vertices, no descendant v of u satisﬁes that h(u, i) ≤ h(v, i + 1). Therefore
no vertex v satisﬁes h(v, i) = h(v, i + 1) in the contracted graph. Hence we canupdate all h by this contracting operation. Since using some binary trees, thetotal time complexity of the trimming algorithm is O(|A| log |V |).

3.2

A Balancing Algorithm

For an arc a, let G be the graph obtained by deleting all arcs sharing theirheads with a except for a. Under the condition that G is a trimmed graph, the

r
r’

x

P’

f

w

u

Fig. 4. Vertices r, r , u, x and w. The paths are Pru and P  .

following lemma holds. Suppose that a dipath from a vertex to an arc is a simple
dipath from the vertex to the head of the arc which includes the arc.
Lemma 6. Let P be a dipath from r to a. If an arc e is included in all DSTs
or no DST of G , then the head of e is on P.
Proof. We state the lemma by proving its contraposition. For an arc e whose
head is not on P, there exists a dipath Q in G from r to e, because of Property
1. If Q includes no arc of G \ G , then it is also included in G . Thus e is included
in some DSTs of G . Otherwise, we consider the subgraph given by Q ∪ P ∩ G .
The subgraph includes a simple dipath from r to e, since the head of e is not
on P. Thus, only arcs which have their heads on P may be included in no DST
of G .
Since G is trimmed, an arc e whose head is not on P shares its head withsome other arcs. The arcs are also included in some DSTs of G . Hence they arealso not included in a DST of G . Therefore any arc included in all DSTs of G
or no DST of G has its head on P.
Let a be an arc sharing its head with a, and P  be a dipath from r to a .
Lemma 7. If an arc e is included in all DSTs or no DST of G \ a, then its headis on P  . In the case that at least two arcs share their heads with a, for any arc
e of the arcs, there are both DSTs including e and not including e.
Proof. G \ a includes the graph obtained by deleting all arcs sharing their heads
with a except for a . Thus, for any arc whose head is not on P  , there are both
DSTs including the arc and those not including the arc in G \ a from Lemma
6. Therefore the ﬁrst assertion is proved.
For any arc of G \ a sharing its head with a , a dipath from r to it does
not include a. Hence, from Property 1, the arc is included in some DSTs of G .
Except for the case that only two arcs a and a have their heads on v, there aresome DSTs not including the arc in G \ a.
By using these lemmas, we select a partitioning arc as follows. Let the weightof a dipath be the number of arcs whose heads are on the path. The weight of

a dipath P is denoted by w(P ). In the balancing phase, we will ﬁnd an arc a∗satisfying the conditions that (a) the weight of a dipath from r to a∗ is at most
3|A|/4, and (b) for an arc a sharing its head with a∗ , the weight of a dipath
from r to the tail of a is at most |A|/2. If an arc a∗ satisﬁes these conditions,G \ a∗ includes at most |A|/2 + 2 arcs which are included in all DSTs or no
DST. Under the condition that |A| ≥ 8, |A|/2 + 2 ≤ 3|A|/4. The graph obtainedby removing all arcs sharing whose heads with a∗ also includes at most 3|A|/4
such arcs. We consider the method for ﬁnding such an arc a∗ .
Let T be a DST of G. To select an arc, we consider the following threecases. (1) If there is a non-back arc (u, v) of T such that w(Pru) ≤ |A|/2 andw(Prv ) ≤ |A|/2, then the arc of T whose head is v satisﬁes the above conditions.
(2) In the other case, let u be the vertex maximizing w(Pru ) among all vertices.
We denote the vertex next to r in Pru by r  . Let P  be a simple dipath from r
to r  not including the arc (r, r  ). P  always exists since G is a trimmed graph.
Let w be the vertex minimizing w(Prw ) among all vertices v of Pru satisfyingthat w(Prv ) > |A|/2. We suppose that x denotes the ﬁrst vertex to appear inP  among vertices v of Pru with w(Prv ) ≤ |A|/2. Since any vertex except r is
the head of at least two arcs, at least 2|V | − 4 arcs of G have their heads not
on w. On the other hand, at most |V | − 1 arcs have their heads on w, thus thenumber of arcs whose heads are w does not exceed |A|/2. Therefore the weightof r  is at most |A|/2, and x always exists in P  . Let f be the arc of P  whose
head is x. We show an example of these vertices and arcs in Figure 3. If the
subpath P  of P  from r to f satisﬁes w(P  ) ≤ |A|/2, then the arc of T sharing
its head with f satisﬁes the conditions (a) and (b).
(3) If f does not satisﬁes these conditions, w(P  ) > |A|/2. From the definition of x, the vertices included in both P  and Prw are at most r and w.
Hence P  includes w since more than |A|/2 arcs have their heads on Prw . Suppose that P1 denotes the path with the smaller weight among Puw and the
subpath of P  from r to w. We also denote the other path by P2 . Let d denote the number of arcs whose heads are w. Since P1 ∩ P2 = {r, w}, we havew(P1 ) ≤ (|A| − d)/2 + d = |A|/2 + d/2 ≤ 3|A|/4, and w(P2 \ w) ≤ |A|/2.
From the above observations, there is an arc satisfying the above two conditions in any trimmed digraph. To ﬁnd such an arc, what we have to do is only
to ﬁnd a DST and some dipaths. They can be done in O(|A| + |V |) time.
By utilizing these algorithms, we obtain a trimming and balancing algorithm.
The algorithm takes O(|A| log |V |) time for an iteration in the worst case. In
the following subsection, we bound the time complexity more tightly by using
the distribution of computation time.

3.3

Bounding the Total Time Complexity

To estimate an amortized time complexity of our algorithm, we ﬁrstly estimate
a lower bound of the number of descendants of a vertex of the enumeration tree
by the following lemma. Let Gx denote the graph which an iteration x inputs.

Lemma 8. If any arc of G is included in a DST and not included in the other
DST, G includes at least |A|/2 distinct DSTs.
Proof. Let T be a DST of G. From Property 1, for any non-tree arc a of T, there
is a simple dipath P from r to a. Hence, for any non-tree arc, we can construct
its own DST T  by adding P to T and deleting some arcs. Since there are atleast |A|/2 non-tree arcs in G, G includes at least |A|/2 DSTs.
From the lemma, we obtain a lower bound D̄(x) = |E(Gx)|/2 of D(x).
Here D(x) is the number of descendants of a vertex x of the enumeration tree,
and E(Gx ) denotes the arc set of Gx . The computation time on a vertex x isO(|E(Gx )| log |V |) time, hence we set T̂ = O(log |V |), and T ∗ = O(log |V |).
From Corollary 1, we can bound the number of excess vertices by the numberαof vertices satisfying that D̄(x) > α+1(D̄(x1 ) + D̄(x2 )) where x1 and x2 are theαchildren of x. If the condition holds, we have that |E(Gx)|/2 > α+1(|E(Gx1 )|/2+
α+1|E(Gx2 )|/2), thus |E(Gxi )| ≤ α |E(Gx)| − |E(Gx)|/4 for each child xi . By
setting α = 8, |E(Gxi )| ≤ (7/8)|E(Gx)|. Therefore any path of the enumeration
tree from the root to a leaf has at most log8/7 |A| excess vertices. We obtainan upper bound X ∗ = log8/7 |A|. From the Theorem 1, we have the following
theorem.
Theorem 9. All DSTs in a digraph can be enumerated in O(|A| log |V | + |V | +N log2 |V |) time and O(|A| + |V |) space where N is the number of DSTs.

Acknowledgments
We greatly thank to Associate Professor Akihisa Tamura of University ofElectro-Communications and all the members of the research group “myogadaniclub” for their kindly advise.

References
1. H.N.Gabow and E.W.Myers, “Finding All Spanning Trees of Directed and Undirected graphs,” SIAM J.Comp.7, pp.280-287 (1978).
2. H.N.Kapoor and H.Ramesh,“Algorithms for Generating All Spanning Trees of
Undirected, Directed and Weighted Graphs,” LNCS.519, Springer-Verlag, pp.461472 (1992).
3. A.Shioura, A.Tamura and T.Uno, “An Optimal Algorithm for Scanning All Spanning Trees of Undirected graphs, ” SIAM J.Comp.26, pp.678-692 (1997).
4. T.Uno, “An Algorithm for Enumerating All Directed Spanning Trees in a Directed
graph,” LNCS 1178, Springer-Verlag, pp.166-173 (1996).
5. T.Uno, “Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs,” LNCS 1350, Springer-Verlag, pp.92-101 (1997).