hide
Free keywords:
-
Abstract:
A minimal blocker in a bipartite graph $G$ is a minimal set of edges the
removal of which leaves no perfect matching in $G$. We give an explicit
characterization of the minimal blockers of a bipartite graph $G$. This result
allows us to obtain a polynomial
delay algorithm for finding all minimal blockers of a given bipartite graph.
Equivalently, this gives a polynomial delay algorithm for listing the
anti-vertices of the perfect matching polytope $P(G)=\{x\in
\RR^E~|~Hx=\be,~~x\geq 0\}$, where $H$ is the incidence matrix of $G$. We also
give similar generation algorithms for other related problems, including
generalized perfect matchings in bipartite graphs, and perfect 2-matchings in
general graphs.
