| ||||||||||||||||||||||||||||||||||||
[RBP10] Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a gridRevue 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
Collaboration:
LAMSADE
BibTeX
|
||||||||||||||||||||||||||||||||||||