Premium
Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
Author(s) -
Boros Endre,
Elbassioni Khaled,
Gurvich Vladimir
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20180
Subject(s) - combinatorics , bipartite graph , mathematics , strong perfect graph theorem , complete bipartite graph , blossom algorithm , discrete mathematics , perfect graph theorem , matching (statistics) , line graph , cograph , foster graph , perfect graph , pathwidth , graph , voltage graph , statistics
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, 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