アイテム詳細

要旨

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.