@inbook{732b4d2c7bca4c6c9a18d4a7a166172e,

title = "Algorithms for generating minimal blockers of perfect matchings in bipartite graphs and related problems",

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 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 ℝE | Hx=e, x ≥ 0}, where H is the incidence matrix of G. We also give similar generation algorithms for other related problems, including d-factors in bipartite graphs, and perfect 2-matchings in general graphs.",

author = "Endre Boros and Khaled Elbassioni and Vladimir Gurvich",

year = "2004",

doi = "10.1007/978-3-540-30140-0_13",

language = "British English",

isbn = "3540230254",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "122--133",

editor = "Susanne Albers and Tomasz Radzik",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}