Minimum d-blockers and d-transversals in graphs

Marie-Christine Costa (), Dominique Werra () and Christophe Picouleau ()
Additional contact information
Marie-Christine Costa: Ecole Nationale Supérieure des Techniques Avancées-Paristech and CEDRIC Laboratory
Dominique Werra: Ecole Polytechnique Fédérale de Lausanne
Christophe Picouleau: Conservatoire National des Arts et Métiers, CEDRIC Laboratory

Journal of Combinatorial Optimization, 2011, vol. 22, issue 4, No 25, 857-872

Abstract: 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 ℘. 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 of stable sets or vertex covers in bipartite and in split graphs.

Keywords: Transversal; Blocker; Cover; Bipartite graph; Split graph; s–t path; s–t cut; Stable set; Bilevel programming (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9334-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:22:y:2011:i:4:d:10.1007_s10878-010-9334-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9334-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().