Graph / Matroid (Bibtex)

P117: Enumeration of all bases of a graphic matroid in a graph

Input:

A graph $G = (V, E)$.

Output:

All bases of a graphic matroid in $G$.

Complexity:

$O(|V| + |E| + N)$ total time and $O(|V| + |E|)$ space.

Comment:

$N$ is the number of solutions. If $G$ is connected, any base is a spanning tree.

Reference:

[Uno1998] (Bibtex)

P118: Enumeration of all bases of a linear matroid in a graph

Input:

A graph $G = (V, E)$.

Output:

All bases of a linear matroid in $G$.

Complexity:

$O(|V|)$ time per solution and $O(|V|^2|E|)$ preprocessing after time.

Comment:

Reference:

[Uno1998] (Bibtex)

P119: Enumeration of all bases of a matching matroid in a graph

Input:

A graph $G = (V, E)$.

Output:

All bases of a matching matroid in $G$.

Complexity:

$O(|V| + |E|)$ time per solution.

Comment:

Reference:

[Uno1998] (Bibtex)