Minimum d-blockers and d-transversals in graphs
2011
Publication type:
Paper in peer-reviewed journals
Journal:
Journal of Combinatorial Optimization, vol. 22-4, pp. 857-872
Publisher:
Springer
HAL:
Keywords :
transversal, blocker, cover, bipartite graph, matching, s. t path, s . t cut, stable set, bilevel programming.
Abstract:
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},
}