MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Boros, Endre
Elbassioni, Khaled M.
Gurvich, Vladimir
dblp
dblp
dblp
Not MPG Author(s):
Boros, Endre
Gurvich, Vladimir
Editor(s):
Albers, Susanne
Radzik, Tomasz
dblp
dblp
Not MPII Editor(s):
Albers, Susanne
Radzik, Tomasz
BibTeX cite key*:
Elbassioni2004g
Title, Booktitle
Title*:
Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
ESA04.pdf (204.31 KB)
Booktitle*:
Algorithms – ESA 2004: 12th Annual European Symposium
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Bergen, Norway
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
14 September 2004
Event End Date:
17 September 2004
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3221
Number:
Month:
September
Pages:
122-133
Year*:
2004
VG Wort Pages:
ISBN/ISSN:
3-540-23025-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2004g,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Gurvich, Vladimir},
EDITOR = {Albers, Susanne and Radzik, Tomasz},
TITLE = {Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems},
BOOKTITLE = {Algorithms – ESA 2004: 12th Annual European Symposium},
PUBLISHER = {Springer},
YEAR = {2004},
VOLUME = {3221},
PAGES = {122--133},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Bergen, Norway},
MONTH = {September},
ISBN = {3-540-23025-4},
}


Entry last modified by Christine Kiesel, 05/02/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni
Created
02/23/2005 02:48:24 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Khaled Elbassioni
Edit Dates
02.05.2007 15:39:19
22.04.2005 14:37:55
21.04.2005 16:37:00
02/23/2005 02:48:24 PM


File Attachment Icon
ESA04.pdf