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
Show more…
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
-
-
Classification
-
Computer science and technology
-
License
-
License undefined
-
Identifiers
-
-
Persistent URL
-
https://folia.unifr.ch/unifr/documents/307896
Statistics
Document views: 62
File downloads:
- blockersandtransversalsi.pdf: 117