Graph / Matching (Bibtex)

P57: Enumeration of the $k$ best perfect matchings of a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ best perfect matchings of $G$ in order.

Complexity:

$O(k|V|^3)$ total time.

Comment:

Reference:

[Chegireddy1987] (Bibtex)

P69: Enumeration of all stable marriage

Input:

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

Output:

All stable marriage of $G$.

Complexity:

$O(|V|)$ time per solution and $O(|V|^2)$ space.

Comment:

Reference:

[Gusfield1989] (Bibtex)

P63: Enumeration of all minimum cost perfect matchings in an weighted bipartite graph

Input:

An weighted bipartite graph $B = (V, E)$.

Output:

All minimum cost perfect matchings in $B$.

Complexity:

$O(|V|(|V| + |E|))$ time per solution and $O(|V| + |E|)$ space

Comment:

Reference:

[Fukuda1992] (Bibtex)

P64: Enumeration of all perfect matchings in a bipartite graph

Input:

A bipartite graph $B = (U, V, E)$, where $|U| = |V|$.

Output:

All perfect matchings in $B$.

Complexity:

$O(c(|V| + |E|))$ total time and $O(|V| + |E|)$ space, after $O(n^{2.5})$ preprocessing time.

Comment:

$c$ is the number of solutions.

Reference:

[Fukuda1994] (Bibtex)

P85: Enumeration of the $k$ best perfect matchings of a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ best perfect matchings of $G$ in decreasing order.

Complexity:

$O(k|V|^3)$ total time with $O(k|V|^2)$ space.

Comment:

Reference:

[Matsui1994] (Bibtex)

P32: Enumeration of all perfect, maximum, and maximal matchings in bipartite graphs

Input:

A bipartite graph $B=(V, E)$.

Output:

All perfect, maximum, and maximal matching in $B$.

Complexity:

$O(|V|)$ time per matching.

Comment:

Reference:

[Uno1997] (Bibtex)

P116: Enumeration of all maximal matchings in a graph

Input:

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

Output:

All maximal matchings in $G$.

Complexity:

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

Comment:

$N$ is the number of solutions and $\Delta$ is the maximum degree in $G$.

Reference:

[Uno2001] (Bibtex)

P132: Enumeration of all minimal blocker in a bipartite graph

Input:

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

Output:

All minimal blocker in $G$.

Complexity:

Polynomial delay and space.

Comment:

A \textit{blocker} of $G$ is an edge subset $X$ of $E$ such that $G' = (U, V, E \setminus X)$ has no perfect matching.

Reference:

[Boros2006] (Bibtex)

P133: Enumeration of all basic perfect 2-matchings in a graph

Input:

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

Output:

All basic perfect 2-matchings in $G$.

Complexity:

Incremental polynomial delay.

Comment:

A \textit{basic 2-matching} of $G$ is a subset of edges that cover the vertices with vertex-disjoint edges and vertex-disjoint odd cycles.

Reference:

[Boros2006] (Bibtex)

P134: Enumeration of all $d$-factor in a bipartite graph

Input:

A bipartite graph $G = (U, V, E)$ and any non negative function $d: A \cup B \to \{0, 1, \cdots, |U| + |V|\}$.

Output:

All $d$-factor in $G$.

Complexity:

$O(|E|)$ delay.

Comment:

A $d$-factor in $G$ is a subgraph $G' = (U, V, X)$ covering all vertices of $G$, whose each vertex $v$ has degree $d(v)$. If for any $v \in U \cup V$, $d(v) = 1$, $G'$ is a perfect matching.

Reference:

[Boros2006] (Bibtex)

P423: Enumeration of all maximal induced matchings in a triangle-free graph

Input:

A triangle-free graph $G$.

Output:

All maximal induced matchings in $G$.

Complexity:

$O(1.4423^n)$ total time with polynomial delay.

Comment:

$n$ is the number of vertices in $G$.

Reference:

[Basavaraju2014] (Bibtex)