Minimum d-blockers and d-transversals in graphs

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"similar to. 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.

Published in:
Journal Of Combinatorial Optimization, 22, 857-872

 Record created 2011-12-16, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)