Matroid / Basis (Bibtex)

P65: Enumeration of all common bases in two matroids

Input:

Two matroids $M_1 = (E, \beta_1)$ and $M_2 = (E, \beta_2)$.

Output:

All $B \in \beta_1 \cap \beta_2$.

Complexity:

$O(|E| ( |E|^2 + t)\lambda)$ total time and $O(|E|^2)$ space.

Comment:

$\lambda$ is the number of common bases and $t$ is time complexity of one pivot operation.

Reference:

[Fukuda1995] (Bibtex)

P326: Enumeration of all basis of a matroid

Input:

A matroid $M$ on the ground set $P$ with rank $m$.

Output:

All basis of $M$.

Complexity:

$O((m|P| + t(Piv))N)$ total time and space complexity independent of $N$.

Comment:

$N$ is the number of solutions. $t(Piv)$ is the time necessary to do one pivot operation.

Reference:

[Avis1996] (Bibtex)