Minimum d-blockers and d-transversals in graphs
2011
Type de publication :
Article (revues avec comité de lecture)
Journal :
Journal of Combinatorial Optimization, vol. 22-4, pp. 857-872
Editeur :
Springer
HAL :
Mots clés :
transversal, blocker, cover, bipartite graph, matching, s. t path, s . t cut, stable set, bilevel programming.
Résumé :
We consider a set V of elements and an optimization problem on V : the search for a maximum (or minimum) cardinality subset of V verifying a given property P. A d-transversal is a subset of V which intersects any optimum solution in at least d elements while a d-blocker is a subset of V whose removal deteriorates the value of an optimum solution by at least d. We present some general characteristics of these problems, we review some situations which have been studied (matchings, s . t paths and s . t cuts in graphs) and we study d-transversals and d-blockers for new problems as stable sets or vertex covers in bipartite graphs.
BibTeX :
@article{Cos-DeW-Pic-2011,
author={Marie-Christine Costa and Dominique de Werra and Christophe
Picouleau },
title={Minimum d-blockers and d-transversals in graphs },
doi={10.1007/s10878-010-9334-6 },
journal={Journal of Combinatorial Optimization },
year={2011 },
volume={22-4 },
pages={857--872},
}