P65: Enumeration of all common bases in two matroids

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)