Blockers and transversals

Zenklusen, Rico; Ries, Bernard; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric

doi:10.1016/j.disc.2009.01.006

Back

Journal article

Blockers and transversals

Zenklusen, Rico ETHZ, Zurich, Switzerland
Ries, Bernard EPFL, Lausanne, Switzerland
Picouleau, Christophe Conservatoire national des Arts et Métiers, Paris, France
de Werra, Dominique EPFL, Lausanne, Switzerland
Costa, Marie-Christine Conservatoire national des Arts et Métiers, Paris, France
Bentz, Cédric Université Paris-Sud, Orsay, France

2009

Published in:

Discrete Mathematics. - 2009, vol. 309, p. 4306-4314

English Given an undirected graph G=(V,E) with matching number \nu(G), we define d- blockers as subsets of edges B such that \nu(G=(V,E\B))\leq \nu(G)-d. We define d- transversals T as subsets of edges such that every maximum matching M has |M\cap T|\geq 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.

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language