[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)

Auteurs: B. Ries , C. Bentz , C. Picouleau , D. de Werra , M.-C. Costa , R. Zenklusen

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

@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",
}