Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid

Bernard Ries, Cédric Bentz, Dominique de Werra,
Marie-Christine Costa, Christophe Picouleau and Rico Zenklusen

2010

Type de publication :

Article (revues avec comité de lecture)

Journal :

Discrete Mathematics, vol. 310 (0), pp. 132--146

Editeur :

Elsevier

DOI :

10.1016/j.disc.2009.08.009

HAL :

hal-00974959

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.

BibTeX :

@article{Rie-Ben-DeW-Cos-Pic-Zen-2010,
    author={Bernard Ries and Cédric Bentz and Dominique de Werra and 
           Marie-Christine Costa and Christophe Picouleau and Rico 
           Zenklusen },
    title={Blockers and Transversals in some subclasses of bipartite 
           graphs: when caterpillars are dancing on a grid },
    doi={10.1016/j.disc.2009.08.009 },
    journal={Discrete Mathematics },
    year={2010 },
    volume={310 (0) },
    pages={132--146},
}