Centre d'Etude et De Recherche en Informatique et Communications (EA4629) |
|
Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
[RBP10] Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
Revue Internationale avec comité de lecture : Journal Discrete Mathematics, vol. 310, pp. 132-146, 2010, (doi:10.1016/j.disc.2009.08.009)
motcle:
Résumé:
Given an undirected graph G = (V;E) with matching number n(G), a d-blocker is a subset of edges B such that n((V;E-B))< ou = n(G)- d and a d-transversal T is a subset of edges such that every maximum matching M has at least d edges in T. While the 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.
Equipe:
oc
| @article { | |||
| RBP10, | |||
| title | = | "{Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid}", | |
| author | = | "B. Ries and C. Bentz and C. Picouleau and D. de Werra and M.-C. Costa and R. Zenklusen", | |
| journal | = | "Discrete Mathematics", | |
| year | = | 2010, | |
| volume | = | 310, | |
| pages | = | "132-146", | |
| doi | = | "10.1016/j.disc.2009.08.009", | |
| } | |||
Agenda
 Suivre le laboratoire
|
ContactsCNAM-CEDRIC ENSIIE-CEDRIC |