(C) Springer Verlag, Lecture Notes on Computer Science

A New Approach for Speeding Up Enumeration
Algorithms and Its Application for Matroid Bases
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 rely on data structures deeply, instead utilizes
analysis of computation time. It speeds enumeration algorithms for directedspanning trees, matroid bases, and some bipartite matching problems. We show
one of these improved algorithms: one for enumerating matroid bases. For a given
matroid M with m elements and rank n, an existing algorithm runs in O(T )time per base. We improved the time complexity to O(T /n), or O(T /m(m − n)).

1

Introduction

Enumeration algorithms for many graph and geometry objects have been developed, and one of the most important and interesting ﬁelds of related to thesealgorithms devoted to making them faster. Although there are numerous algorithms and numerous ways to improve enumeration algorithms, especially forspanning trees and paths, no general technique or framework for their improvements has been proposed. Most enumeration algorithms have been taking advantage of data structures that speed their iterations. So if we can not speed theiterations, we cannot obtain a fast algorithm in the usual way.
In this paper, we describe a new approach, “trimming and balancing” tomaking enumeration algorithms faster. It is not based on the use of data structures and it speeds enumeration algorithms without speeding iterations. It canthus be used to improve many enumeration algorithms that have not been improved in the usual way. By applying our approach, we can reduce the timecomplexity of the enumeration algorithm for perfect matchings from O(m) per
matching to O(n), that of the enumeration algorithm for maximum matchingsfrom O(m) per matching to O(n), and that of the enumeration algorithm fordirected spanning trees from O(n) per tree to O(log n). Here m and n denote thenumber of edges and vertices of the given graph. In this paper, we also reportan enumeration algorithm for matroid bases that has improved by using thetrimming and balancing approach. The problem of enumerating matroid bases
includes some other enumeration problems, spanning trees and maximal sets of
independent columns of a matrix. There are some studies on enumeration algorithms for these problems, especially spanning trees [2, 1]. Although several
algorithms achieve optimal time and space complexities, they require the use ofdata structures that are not simple. Our Trimming and Balancing algorithms forthese problems attain smaller, or at least not larger time complexities without
using complicated data structures.
Our approach adds two new phases to an enumeration algorithm, which wecall a trimming phase and a balancing phase. An iteration of a modiﬁed algorithm may take much more computation time than that of the original algorithm,

but the total time complexity of the modiﬁed algorithm is often considerably
smaller than that of the original algorithm. Some our algorithms take much
more computation time in an iteration than the original algorithm, but it attains smaller time complexities. In the next section, we describe the frameworkof trimming and balancing. A trimming and balancing algorithm surely terminate in short time, but to prove it is not so easy by using usual analysis of timecomplexity. Hence we also describe a technique for analyzing time complexities
in the next section.

2

Framework of Trimming and Balancing

To explain the concept of trimming and balancing, we use here a simple binary
partition algorithm for enumerating of all the bases in the given matroid M.
The structure of the algorithm is quite simple. For a given matroid M = (E, I),
we denote the cardinality of its grand set by m and we denote its rank by n.
For a base B of M, we denote the elementary circuit of e ∈/ B by Cir(B, e). We
also denote the elementary cut set of an element e ∈ B by Cut(B, e). For anelement e of M, we denote the matroid obtained by contracting e by M/e, andthe matroid obtained by deleting e by M \ e. To obtain elementary circuits andelementary cuts, the simple algorithm uses an independent set oracle algorithm,
or an elementary circuit oracle algorithm. The former checks whether the given
set is independent or not, and the latter outputs the elementary circuit includedin the union of the given base and element. We denote the time complexity ofthese oracle algorithms by Tind (m, n) and Tcir (m, n). To contract and delete
an element of the matroid, we use matroid subroutines whose time complexity
are denoted by Tcnt (m, n) and Tdel (m, n). Assume that the contraction and thedeletion of k elements simultaneously also take only Tcnt (m, n) and Tdel (m, n)time.
By using these algorithms, we can obtain a simple binary partition algorithm.
For a given matroid M = (E, I) and its base B, we ﬁnd a partitioning elemente ∈ B and an element f ∈/ B such that B \ e ∪ f forms a base. If there is anotherbase in M, such a pair of elements always exists. We spend O((m−n)Tcir (m, n))or O((m − n)nTind (m, n)) time to ﬁnd them. By using e, we divide the problem into two subproblems: enumerating all bases including e and enumerating
all those not including e. All bases including e are bases of M/e. All bases notincluding e are also bases of M \ e. Hence they can be enumerated by recursive
calls: one inputs M/e, and the other inputs M \ e. Thus we obtain an enumeration algorithm simply by using algorithms for constructing these two matroids,
and it runs in O((m− n) min{Tcir (m, n), nTind (m, n)} + Tcnt (m, n) + Tdel (m, n))time. We denote the computation time by T (m, n).
Our trimming and balancing approach reduces the time complexity of enumeration algorithms like this one by adding a trimming phase and a balancing
phase. The trimming phase removes unnecessary parts from the input. In theabove algorithm considered here, for example, unnecessary parts are elements
included in all bases, or included in no base. These elements can be contracted
or removed, hence we can transform the problem into a smaller one. The newproblem includes many outputs for its size rather than the original problem.
We show in a later section that a matroid M including no unnecessary element
contains Ω(n(m−n)) bases. By the trimming phase, the computation time of aniteration will be not so large for the number of outputs, so the total computation
time per output will be small.
The trimming phase does not always decrease the total computation time.
Suppose that the algorithm input is a matroid composed of one circuit {e1 , ..., em}.
As we can see, no element is unnecessary. Now we suppose that the algorithmchooses the element e1 as a partitioning element. Since only one base does not include e1 , one of the subproblems terminates immediately. To construct the othersubproblem, e1 is contracted and we obtain a matroid almost identical to theoriginal matroid: one composed of only one circuit with m − 1 elements. Hencethe total computation time will be O(T (m, m−1)+T (m−1, m−2)+...+T (2, 1)).
Under the condition that T (m, n) is polynomial, the sum is O(mT (m, n)), whichis O(T (m, n)) per base.
Why does the worst case running time not decrease? The answer is thatthe way of partitioning the problem is not good. We therefore reduce the timecomplexity by adding a balancing phase. It partitions the original problem into
“good subproblems” such as subproblems that are not small after trimming by,
for example, choosing a good element for partitioning. If we add a balancing
phase, the structure of the recursion will be balanced. Hence, if the number of
outputs is small for the input size, then the both of the subproblems generated
will be small, and the total time complexity will also be small.
The problem of enumerating bases of a circuit can be partitioned into one
subproblem which is to enumerate bases including elements {e1 , ..., em/2}, andanother subproblem which is to enumerate bases including {em/2+1 , ..., em}. All
the bases include m−1 elements of {e1 , ..., em}, the problem is surely partitioned.
By using this partitioning rule in this case, we can partition the problem into
two subproblems of almost equal sizes, thus the total computation time will be
reduced to O((log m)T (m, m − 1)) or smaller. In fact, this way of trimming can
not attain our result. In later section, we describe the other way of trimming
which is utilized in our algorithm for enumerating matroid bases.
Next we show our technique for analyzing the time complexity of enumeration algorithms. Before explaining our analysis, we introduce a virtual tree whichis called an enumeration tree. Enumeration tree is deﬁned for an enumeration
algorithm and an input, and captures the structure of the recursive calls occurring in the algorithm. For a given enumeration algorithm and its input, let
V be a vertex 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 thevertices 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 startof the algorithm. To analyze enumeration algorithms, we show some propertiesof enumeration trees which are satisﬁed for any input.
To analyze the time complexity of an enumeration algorithm, we consider
the following distribution rule on the enumeration tree. Let D(x) be the numberof descendants of a vertex x of T , and T (x) be an upper bound of the computation time on x. Suppose that T̂ is an upper bound of maxx∈T {T (x)/D(x)}.
Our analysis uses an arbitrary constant number α. Using these upper bounds
and this constant, we distribute the computation time. The distribution is done

from a parent vertex to its children in the top-down manner. Let Tp (x) be thecomputation time distributed to x by the parent of x. x has computation timeTp (x)+T (x). We store αT̂ of Tp (x)+T (x) on x, and distribute Tp (x)+T (x)−αT̂
to the children of x. We have two distribution rules type 1 and 2 as the following. In each case, we distribute the computation time of each child recursively. Type 1 is that each child y receives computation time proportional to
the number of the descendants of y. The computation time distributed to y is
(Tp (x)+T (x)−αT̂ )D(y)/(D(x)−1). Type 2 is that each child y receives computation time proportional to the computation time of y. If a child y receives morethan αT̂ D(y) then we distribute as the same way of type 1. The computation
time distributed to y is (Tp (x) + T (x) − αT̂ )T (y)/(D(x) − 1).
By this distribution rule, some vertices may receive much computation time.
Thus we deﬁne excess vertices as those satisfying Tp (x) + T (x) > αT̂ D(x) and
we stop the distribution on the excess vertices. The children of an excess vertex
receive no computation time from their parent. Note that the above distribution
rule is also applied to the descendants of excess vertices. By this new rule, Tp (x)for any vertex x is bounded by αT̂ D(x) since the computation time distributed
from a parent to its child is proportional to the number of descendants of thechild.
After this distribution, no vertex except excess vertices has more than O(T̂ )on it. We then distribute the computation time on each excess vertex to all its
descendants uniformly. Since the computation time on any excess vertex x isbounded by (α + 1)T̂ D(x), each descendant receives at most (α + 1)T̂ time froman excess ancestor. Let X ∗ be an upper bound of the maximum number of theexcess vertices on a path from the root to a leaf. Using X ∗ , we have an upperbound O(T̂ X ∗ ) of the time complexity per iteration. From these, we obtain thefollowing theorem.
Theorem 1. An enumeration algorithm runs in O(T̂ X ∗ ) time per iteration. 
Our analysis requires T̂ and X ∗ . To obtain a good upper bound of the computation time, 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).
Although it is hard to identify excess vertices in the enumeration tree, we canobtain an eﬃcient upper bound. Let x and y be excess vertices such that y is anancestor of x and no other excess vertex is in the path Pyx from y to x in theenumeration tree. Note that Pyx has at least one internal vertex.
Lemma 2. If we use type 2 rule
on all vertices, a vertex w of Pyx \ y satisﬁes
the condition that T (w) > α−1u∈C(w) T (u) where C(w) is the set of children
αof w.
Proof. We show that all vertices w of Pyx \ y satisfy the condition that Tp (w) <(α−1)T̂ (w) under the assumption that Pyx \y includes no such vertex. Any childof y satisﬁes the condition since y is an excess vertex. Suppose that a vertex w
of Pyx \ y satisﬁes the condition that Tp (w ) ≤ (α − 1)T (w ), where w  is theparent of w. From the assumption, we haveTp (w) = ((Tp (w ) + T (w ) − αT̂ )T (w)) / ( u∈C(w ) T (u))

≤ (αT (w )T (w)) / ( u∈C(w ) T (u))
= (α − 1)T (w)≤ (αT (w) α−1u∈C(w) T (u)) / (u∈C(w  ) T (u))α

Since T (w) ≤ T̂ D(w), we have Tp (w) ≤ (α −1)T̂ D(w). This implies that Tp (x)+T (x) ≤ αT̂ D(x), and contradicts that x is an excess vertex.
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 3. If we use type 1 rule on all vertices
 and T̂ α= maxx∈T {T (x)/D̄(x)},a vertex w of Pyx \ y satisﬁes that D̄(w) > u∈C(w) α+1
D̄(u).

These conditions can be easily checked, and are often suﬃcient to analyze.
In the next section, we describe a trimming and balancing algorithm for matroidbases. To see trimming and balancing algorithms for directed spanning trees orperfect matchings, refer [3, 4].

3

Trimming and Balancing Algorithms for Matroid Bases

In this section, we describe algorithms for trimming phase and balancing phaseof our enumeration algorithm for matroid bases. Our trimming algorithm is quite
simple. For a given matroid, if an element of the grand set forms a circuit, thenit is included in no base. We call the element a loop. In the matroid obtainedby deleting all loops, the set of bases is preserved. If the elementary cut ofan element is composed of only the element, it is included in all bases. Theseelements can be contracted. The trimming algorithm contracts or deletes these
unnecessary elements. These conditions for all elements can be checked by ﬁnding
the elementary circuits for all elements outside a base. This can be done inO((m − n) min{nTind (m, n), Tcir (m, n)}).
We next consider the balancing algorithm. By partitioning the given matroid, we obtain two matroids M/e and M \ e. If one is a suﬃciently smaller
than the other after trimming, the enumeration tree of the algorithm may bebiased. Hence we use a balancing algorithm to avoid it. To obtain our balancing
algorithm, we use the following properties of M/e and M \ e for a base B of M.
Property 1 Suppose that e ∈ B and B  is the base of M/e obtained by B \ e.
The following conditions hold for M/e and B  . (1) For any element f ∈/ B, thediﬀerence between Cir(B, f) and Cir(B  , f) is either e or nothing. (2) For any
element f ∈ B \ e, Cut(B, f) = Cut(B  , f).

Property 2 The following conditions hold for e ∈/ B. (1) For any element f ∈/B, the elementary circuits of f on B in M and of f on B in M\ e are equal. (2)For any element f ∈ B, the diﬀerence between the elementary cuts Cut(B, f) in
M and Cut(B, f) in M \ e is either nothing or e.

Using these properties, we construct the balancing algorithm. First we examine the case in which some elements of E are loops in M/e. In this case, we
partition the original problem in a way that is based on the following properties.
Property 3 For two elements e and e of E such that {e, e } is a circuit, B isa base including e if and only if B \ e ∪ e is a base.

Since M is trimmed, any loop {e } of M/e composes a circuit of M withe. Thus we can see that all bases of M including a loop e of M/e can beenumerated by enumerating all bases including e. All bases including e areconstructed from the bases including e simply by replacing e with e .
Suppose that e2 , ..., ek are loops in M/e1 . We then divide the problem into
the subproblems of enumerating bases including each ei , and of enumeratingbases not including any ei . Since any matroid M/ei can be constructed from
M/e1 simply by renaming e1 to ei , the time complexity of an iteration does notincrease.
Next we examine the case in which some elements of M \ e have elementary
cuts consisting of only those elements. The partitioning method we use in thiscase is based on the following lemma.
Lemma 4. For a trimmed matroid M, let e1 , ..., ek be elements satisfying thecondition that any base not including e1 always includes e2 , ..., ek. All bases include at least k − 1 of these elements.
Proof. Suppose that there is a base not including ei and ej . From the assumption,ei and ej are not e1 . Since M is trimmed, by removing e1 and adding an element
to the base, we obtain a base not including e1 and ej , or not including e1 andei . This contradicts the assumption.

Lemma 5. Let e1 , ..., ek be elements satisfying the condition that any base notincluding e1 always includes e2 , ..., ek. For any base not including e1 , there isa base obtained by exchanging e1 and ei . Conversely, for any i and any baseincluding e1 , there is a base obtained by exchanging e1 and ei .
Proof. To prove this lemma, we show that any circuit includes all ei , or includes
no ei . Suppose that a circuit C includes ei and does not include ej . By removing
ei from C, we can obtain an independent set. Let B be a base including theindependent set. From Lemma 4, B includes ej . Since the matroid is trimmed,
there is a base not including ej . Hence there is an element e whose elementary
circuit includes ej . Since Cir(B, ei ) is C, e is not ei . By exchanging e and ej ,we obtain a base including neither ei nor ej . This contradicts Lemma 4.
We now have that any circuit includes all ei or no ei . Hence for any base notincluding e1 , we have a base obtained by exchanging e1 and ei . For any i andany base including e1 , we also have a base obtained by exchanging e1 and ei . Let us consider that e2 , ..., ek are included in any base of M \ e1 . In thiscase, we partition the problem into the subproblems of enumerating all bases
not including each ei and of enumerating all bases including all ei . Since any
matroid M \ ei can be constructed from M \ ei by renaming e1 to ei , each
additional subproblem is constructed in O(1) time. We now describe the detailsof the algorithm as follows. Assume that M is trimmed.
ALGORITHM: T&B for Matroid Bases (M)Step 1: Choose an element e ∈ B.
Step 2: Find a base B  not including e.
Step 3: Generate and trim M/e and M \ e.
Step 4: If one of the subproblems loses some elements, partition the problem
again by using the balancing algorithm.
Step 5: Solve the subproblems by recursive calls.

This algorithm takes O(T (m, n)) time on an iteration. we bound the total
time complexity by a quite small order with the use of our analysis in the next
section.

4

Bounding the Amortized Time Complexity

To analyze the time complexity, we use the enumeration tree T of our algorithm.
For a vertex x of T , we denote the matroid by Mx. which a recursive callcorresponding to a vertex x inputs. Since x corresponds to an iteration, leaves
correspond to bases one-to-one, and any internal vertex has at least two children.
Hence the number of iterations does not exceed twice the number of bases. We
denote the size of the grand set of Mx by mx and the rank by nx .
We ﬁrst establish a lower bound D̄(x). It is given by the lower bound on thenumber of bases in a trimmed matroid.
Lemma 6. A trimmed matroid M includes at least (m − n)n bases.
Proof. We prove the lemma by induction. Let B be a base of M. For eachelement e in B, there is an element not in B whose elementary circuit includes
e. By exchanging e and the element, we obtain another base of M. The generated
bases are distinct, hence we have at least n other bases in the matroid. For eachelement e not in B, we have an elementary circuit including at least one elementof B. By exchanging e and an element of the circuit, we can obtain m−n distinct
bases. Hence we have at least m−n bases in the matroid. Therefore the conditionof the lemma holds if n = 1 or m − n = 1.
Assume that the condition of the lemma holds if m − n < k and n ≤ k hold, or m − n ≤ k and n < k  hold. Under this assumption, we prove thatthe condition of the lemma holds for the matroid M with m − n = k > 1 andn = k  > 1. Let e be an element of the grand set of M. If the matroids M/eand M \ e lose no element by the trimming algorithm, M includes at least(m − n − 1)n + (m − n)(n − 1) = 2(m − n)n − m bases. Since m − n and n > 1,
we have 2(m − n)n − m > (m − n)n.
Let us consider the other cases. If M/e loses k (1 ≤ k ≤ m − n) elements
by the trimming algorithm, then the balancing algorithm partitions the bases of
M to bases of at least k + 1 trimmed matroids with m − k − 1 elements and therank n − 1. Since these matroids have at least (m − k − 1 − (n − 1))(n − 1) bases
from the assumption, M has at least (k + 1)(m − k − n)(n − 1) ≥ (m − n)n bases.
In the case that M \ e loses k (1 ≤ k ≤ n) elements, the bases of M arepartitioned to bases of k + 1 matroids with m − k − 1 elements and the rankn − k. Since all these matroids have at least (m − k − 1 − (n − k))(n − k) bases by
the assumption, M has at least (k + 1)(m − n − 1)(n − k) ≥ (m − n)n bases. 
Next we set X ∗ to an upper bound on excess vertices. We set α to 30.
From Corollary 3, for X ∗ , we can use an upper bound of the number of vertices
x in 
a path from the root to a leaf satisfying the condition (a) that D̄(x) <αu∈C(x) D̄(u). We show which vertices of T satisfy the condition. We ﬁrst
α+1
consider the case that mx − nx = 1 or nx = 1. In this case, the balancing
algorithm generates mx − nx or nx subproblems with only one element in the
grand set. This element may be an excess vertex, although the number of thistype of excess vertices in the path from the root to a leaf is at most 1.

Next we consider the case that mx − nx, nx > 1. If both generated subproblems of x lose no element by the trimming algorithm, the number of bases
included in M/e or M \ e is at least (mx − nx − 1)nx + (mx − nx)(nx − 1) =2(mx −nx )nx −mx . For a ﬁxed mx , (mx −nx )nx takes its minimum value 2mx −2
when nx = 2 and nx = mx − 2. Since 2mx − 2 ≥ mx /30 for any mx > 2, we have(mx − nx )nx ≤ 29
30 (2(mx − nx )nx − mx ). Hence x does not satisfy the condition(a). Suppose that x is an excess vertex. Then a subproblem of x loses k elements
by the trimming algorithm. Thus we have 30(mx − nx)nx > (k + 1)(mx − k −2930nx )(nx − 1) or 29 (mx − nx )nx > (k + 1)(mx − nx − 1)(nx − k) from the proof ofx −k−nx)
x−nx )x −k)x> (k+1)(m, or 1.04(m> (k+1)(n.
lemma 6. Hence we have 1.04n
nx −1(mx −nx )mx −nx −1
nx
The former condition holds only for k > mx −nx −4, and the latter condition
holds only for k > nx − 4. Thus any child y of x satisﬁes m − n ≤ 4 or n ≤ 4.
The rank and the cardinality of the grand set decrease strictly in the children,
hence there are at most 8 the above excess vertices in a path from the root to aleaf. Therefore we can set X ∗ to 9.
Since T (x) =O(T (mx , nx)), we set T̂ to maxx{O(T (mx , nx)/D̄(x))} =O(T (m, n)/(mx − nx )nx ). We obtain the following theorem.
Theorem 7. We can enumerate all matroid bases in O(T (m, n)) preprocessing
time and O(T (m, n)/n(m − n)}) time per base, if the time complexities of oracle
algorithms are depend on the input size of contracted and deleted matroids. 

5On Graphic Matroids

In the following sections, we show some applications of our algorithm for someenumeration problems of matroid bases. Here we see the case of graphic matroids. The grand set of a graphic matroid M is given by the edge set E of anundirected graph G = (V, E), and its independent set is given by a forest of thegraph. If the graph is connected, any base is a spanning tree. Hence the problem is that of enumerating all spanning trees of given undirected graphs. There
are numerous studies for this problem, and numerous algorithms have been proposed and improved. The time complexities of the enumeration algorithms havebeen reduced from O(|E| + |V |) to O(|V |) and to O(1) per spanning tree. And
their space complexities have been reduced from O(|V ||E|) to O(|E| + |V |). The
methods by which these algorithms were improved relied on some advanced data
structures, but our algorithm in this subsection requires neither complicated algorithm nor advanced data structure.
Since any spanning tree of G has |V | − 1 edges, we have that the number of
elements m is |E| and the rank n is |V | − 1. A base of a graphic matroid canbe found by a graph search algorithm in O(m + n) time. The contraction andthe deletion of the matroid are also easy. M/e is given by the graph obtainedby contracting the edge e, and M \ e is given by the graph obtained by deletinge. Since any independent set of the matroid includes no cycle, a circuit of thematroid is a cycle in G. Thus an elementary circuit oracle algorithm with O(n)running time can be constructed.
We thus have Tcnt (m, n) = O(n), Tdel (m, n) = O(m − n), and Tcir (m, n) =O(n). The time complexity of an iteration of the trimming and balancing algorithm using these oracle algorithms is bounded by O((m − n)n). Since all loops
are detected in O(m) time and all elements with elementary cuts composed ofonly themselves can be found by the 2-connected component decomposition inO(m+n) time, the time complexity of the trimming algorithm can be reduced toO(m+ n). Therefore the trimming and balancing algorithm takes O(m+ n) time
for preprocessing and O( O((m−n)n) ) = O(1) time per spanning tree. It requires(m−n)nonly O(m + n) memory. These complexities are equal to those of the optimalalgorithm reported by Shioura et al.[2]. Here we have the following theorem.
Theorem 8. All bases of a graphic matroid can be enumerated by a trimmingand balancing algorithm in O(m + n + N ) time and O(m + n) memory where N
denotes the number of bases.
6

On Linear Matroids

For an m-by-n matrix M with m > n, the grand set of the linear matroid
is given by the set of column vectors, and an independent set is given by aset of independent column vectors. The independent set family is given by thecorrection of all the independent sets. If the given matrix is not degenerate,
the bases of the linear matroid are all submatrices composed of n independent
column vectors. For a given non-singular m-by-n matrix, we consider the problem
of enumerating all these n-by-n non-singular submatrices, which are composedof n independent column vectors. For this problem, Y. Matsui [1] proposed an
enumeration algorithm with a time complexity of O(n2 ) per base.
A base of the linear matroid can be found easily. By some LDL or LU decomposition algorithms, we can obtain a non-singular submatrix B in at mostO(n2 m) time. Our algorithm for linear matroids utilizes an elementary circuit oracle algorithm. To obtain a fast elementary circuit oracle algorithm, we consider
a linear matroid equivalent to M. The matroid is given by a matrix U (M, B)
generated from M as follows. All ith column vectors of B are replaced by theunit vector ei whose ith element is 1 and other elements are 0. A column vectorx ∈/ B is replaced by the vector y satisfying By = x. Since a set of column
vectors of M is independent if and only if the set of column vectors corresponding to them is independent in U (M, B), the linear matroid given by U (M, B) is
equivalent to M. We enumerate bases of the matroid instead of the bases of M.
As column vectors of B are unit vectors, the elementary circuit of a column
vector x can be found easily. The ith column vector of B is in Cir(B, x) if andonly if the ith element of x is not 0. In each iteration, we exchange ith column
vector of B and the other column vector x and thereby obtain the other base B  .
x is generally not a unit vector, thus we have to obtain U (M, B  ). Since only x
is not a unit vector in B  , for any column vector z of M, we can obtain a vector
y satisfying B  y = z in O(n2 ) time. Thus we take O(n2 (m − n)) time to obtain
U (M, B  ).
We next show contract and delete operation of an element. The deleting
operation is simple, since it involves only the deletion of a column vector. And
because in each iteration we delete a column vector outside the base, we do notneed to obtain U (M, B  ). To contract the matroid by the ith column vector xi ,we ﬁx xi in B and consider only the bases including xi . Since xi is included inany base, we can restrict the rest of the column vectors to the linear subspaceorthogonal to xi . Hence we consider the matrix obtained by deleting ith elementfrom all column vectors of M. As the linear matroid given by the matrix isequivalent to M/xi , we enumerate the bases of the matroid instead of the basesof M/xi .
Because each of the above operations takes at most O(n2 (m−n)) time, for an
iteration x inputting an mx -by-nx matrix, the time complexity is O(n2x (mx −nx ))Since n2 (m − n)/n(m − n) = n, we obtain the following theorem.
Theorem 9. All bases of the linear matroid given by an m-by-n matrix are
enumerated in O(n2 m) preprocessing time and O(n) time per base.
7

On Matching Matroids

Matching matroids are given by bipartite graphs. For a bipartite graph G = (V1 ∪V2 , E), the grand set of a matching matroid is given by V1 , and an independent
set of the matroid is given by a set of vertices of V1 covered by a matching of G.
A base B of a matching matroid is obtained by ﬁnding a maximum cardinality
matching M of G. For a vertex v ∈ V1 \ B, u ∈ B is in Cir(B, v) if and only ifthere is an alternating path from v to u in G. An alternating path is a path of G
satisfying that edges in M and edges not in M appear in the path alternatively.
By exchanging edges of M and the other edges along the alternating path fromv to u, we obtain the other maximum matching M  which covers v and does notcover u. To obtain the elementary circuit of v, we ﬁnd the vertices of the base towhich there are some alternating paths from v. We can ﬁnd them in O(m + n)time by using a graph search algorithm [3].
To delete a vertex from a matching matroid is easy. It is done by deleting thevertex from G. The contracted matroid is not obtained by reforming G. Instead,
we simply mark the vertex to contract, and never output marked vertices when
we ﬁnd elementary circuit. By this modiﬁcation of the elementary circuit oracle
algorithm, we can obtain the contracted matching matroid.
An iteration x takes O((|Ex | − |Vx|)(|E| + |V |)) time where Ex and Vx denotethe edge set and vertex set of the input graph of x. Note that E is the edge setof the graph of the original problem. From our analysis, we know that the timex |)(|E|+|V |))complexity of this enumeration algorithm is O((|E|Vxx|−|V= O(|E|+|V |)|(|Ex |−|Vx|)
per iteration. Therefore we have the following theorem.
Theorem 10. All bases of a matching matroid given by a bipartite graph G =(V, E) can be enumerated in O(|E| + |V |) time per base.


References
1. Y. Matsui, “An Algorithm for Generating All the Bases of Equality Systems ,” Research Report, Dept. of Math. Engineering and Info. Physics, University of Tokyo,
Tokyo (to appear).
2. 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).
3. T.Uno, “Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs,” LNCS 1350, Springer-Verlag, pp.92-101 (1997).
4. T.Uno, “A New Approach for Speeding Up Enumeration Algorithms”
LNCS 1533, Springer-Verlag, pp.287-296 (1998)