Algorithms for generating minimal blockers of perfect matchings in bipartite graphs and related problems

Endre Boros, Khaled Elbassioni, Vladimir Gurvich

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

3 Scopus citations

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.

Original languageBritish English
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsSusanne Albers, Tomasz Radzik
PublisherSpringer Verlag
Pages122-133
Number of pages12
ISBN (Print)3540230254, 9783540230250
DOIs
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3221
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Algorithms for generating minimal blockers of perfect matchings in bipartite graphs and related problems'. Together they form a unique fingerprint.

Cite this