de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons43989

Albers,  Susanne
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Boros, E., Elbassioni, K., & Gurvich, V. (2004). Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems. In Algorithms – ESA 2004: 12th Annual European Symposium (pp. 122-133). Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2A12-5
##### 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, 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.