Minimum d‐blockers and d‐transversals in graphs

Minimum d‐blockers and d‐transversals in graphs

0.00 Avg rating0 Votes
Article ID: iaor201111144
Volume: 22
Issue: 4
Start Page Number: 857
End Page Number: 872
Publication Date: Nov 2011
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: graphs, heuristics
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, st paths and st cuts in graphs) and we study d‐transversals and d‐blockers of stable sets or vertex covers in bipartite and in split graphs.

Reviews

Required fields are marked *. Your email address will not be published.