|
 
|
[CDP11] Minimum d-blockers and d-transversals in graphs
Revue Internationale avec comité de lecture : Journal J. of Combinatorial Optimization, vol. 22(4), pp. 857-872, 2011, (doi:10.1007/s10878-010-9334-6)
motcle:
Résumé:
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.
Keywords: transversal, blocker, cover, bipartite graph, matching,
s.
t path,
s
.
t cut, stable set, bilevel programming.
Equipe:
oc
BibTeX
| @article { | |||
| CDP11, | |||
| title | = | "{Minimum d-blockers and d-transversals in graphs}", | |
| author | = | "M.-C. Costa and D. de Werra and C. Picouleau", | |
| journal | = | "J. of Combinatorial Optimization", | |
| year | = | 2011, | |
| volume | = | 22, | |
| number | = | 4, | |
| pages | = | "857-872", | |
| doi | = | "10.1007/s10878-010-9334-6", | |
| } | |||
