Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
Endre Boros, Khaled Elbassioni, Vladimir A. Gurvich · Journal of Graph Theory · 2006
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, we obtain a polynomial delay algorithm for listing the anti-vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d-factors in bipartite graphs, and perfect 2-matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006