Blockers and Transversals

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

2009

Publication type:

Paper in peer-reviewed journals

Journal:

Discrete Mathematics, vol. 13, pp. 4306--4314

Publisher:

Elsevier

ISBN:

0012-365X

DOI:

10.1016/j.disc.2009.01.006

HAL:

hal-00975349

Keywords :

transversal, blocker, matching, complete graph, complete bipartite graph, tree.

Abstract:

We explore connections between d-blockers B in a graph G = (V;E) (i.e. subsets of edges whose removal decreases by at least d the cardinality of maximum matchings) and d-transversals T (i.e. subsets of edges such that every maximum matching M has at least d edges in T. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, grid graphs, chains and cycles. We also study the complexity status of finding minimum transversals and blockers. Algorithms for d-transversals and d- blockers based on dynamic programming are given for trees.

BibTeX:

@article{Zen-Rie-Pic-DeW-Cos-Ben-2009,
    author={Rico Zenklusen and Bernard Ries and Christophe Picouleau and 
           Dominique de Werra and Marie-Christine Costa and Cédric Bentz },
    title={Blockers and Transversals },
    doi={10.1016/j.disc.2009.01.006 },
    journal={Discrete Mathematics },
    year={2009 },
    volume={13 },
    pages={4306--4314},
}