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

Publication type:

Paper in peer-reviewed journals

Journal:

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

Publisher:

Elsevier

DOI:

10.1016/j.disc.2009.08.009

HAL:

hal-00974959

Abstract:

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