P134: Enumeration of all $d$-factor in a bipartite graph
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.