English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

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

MPS-Authors
/persons/resource/persons44374

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

/persons/resource/persons43989

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
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: https://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.