Loading...
research article
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.
Type
research article
Web of Science ID
WOS:000296520200025
Authors
Publication date
2011
Published in
Volume
22
Start page
857
End page
872
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
December 16, 2011
Use this identifier to reference this record