Loading...
research article
Blockers and transversals
2009
Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) <= nu(G) - d. We define d-transversals T as subsets of edges such that every maximum matching M has |M boolean AND T| >= d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, chains and cycles and we construct minimum d-transversals and d-blockers in these special graphs. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs. (C) 2009 Elsevier B.V. All rights reserved.
Type
research article
Web of Science ID
WOS:000266760400013
Authors
Zenklusen, Rico
•
Ries, Bernard
•
Picouleau, Christophe
•
de Werra, Dominique
•
Costa, Marie-Christine
•
Bentz, Cédric
Publication date
2009
Published in
Volume
309
Issue
13
Start page
4306
End page
4314
Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
September 30, 2010
Use this identifier to reference this record