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
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 324622
- DOI 10.1016/j.disc.2009.01.006
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307896
Statistics
Document views: 70
File downloads:
- blockersandtransversalsi.pdf: 168