Blockers and transversals in some subclasses of bipartite graphs : When caterpillars are dancing on a grid
-
Ries, Bernard
Columbia University, United States
-
Bentz, Cédric
Université Paris-Sud
-
Picouleau, Christophe
CNAM, France
-
de Werra, Dominique
EPFL, Switzerland
-
Costa, Marie-Christine
ENSTA, France
-
Zenklusen, Rico
ETHZ, Switzerland
Show more…
Published in:
- Discrete Mathematics. - 2010, vol. 310, p. 132-146
English
Given an undirected graph G=(V,E) with matching number \nu(G), a d-blocker is a subset of edges B such that \nu(/V,E\B))<=\nu(G)-d and a d-transversal T is a subset of edges such that every maximum matching M has |M \cap T|>= d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the special cases where G is a grid graph or a tree.
-
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/308018
Statistics
Document views: 45
File downloads:
- blockersandtransversalsii.pdf: 129