Index
Problem list
Graph
Matching
References
TODO list
P132
: Enumeration of all minimal blocker in a bipartite graph
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
)