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.
Type de document :
Article dans une revue
Journal of Combinatorial Optimization, Springer Verlag, 2011, 22 (4), pp.857-872. 〈10.1007/s10878-010-9334-6〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal-ensta.archives-ouvertes.fr/hal-00973849
Contributeur : Aurélien Arnoux <>
Soumis le : mardi 5 avril 2016 - 15:27:52
Dernière modification le : mercredi 6 décembre 2017 - 16:46:01
Document(s) archivé(s) le : mercredi 6 juillet 2016 - 14:40:17

Fichier

ArticleJOCO.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

107

Téléchargements de fichiers

68