Minimum d-blockers and d-transversals in graphs

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-ensta-paris.archives-ouvertes.fr//hal-00973849
Contributor : Aurélien Arnoux <>
Submitted on : Tuesday, April 5, 2016 - 3:27:52 PM
Last modification on : Wednesday, July 3, 2019 - 10:48:04 AM
Long-term archiving on: Wednesday, July 6, 2016 - 2:40:17 PM

File

ArticleJOCO.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marie-Christine Costa, Dominique de Werra, Christophe Picouleau. Minimum d-blockers and d-transversals in graphs. Journal of Combinatorial Optimization, Springer Verlag, 2011, 22 (4), pp.857-872. ⟨10.1007/s10878-010-9334-6⟩. ⟨hal-00973849⟩

Share

Metrics

Record views

187

Files downloads

170