Transversal hypergraphs to perfect match
โ
Endre Boros; Khaled Elbassioni; Vladimir Gurvich
๐
Article
๐
2006
๐
John Wiley and Sons
๐
English
โ 285 KB
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