|
 
|
[CCP15a] A general framework for finding d-transversals in graphs
Conférence Internationale avec comité de lecture : EURO, July 2015, pp.1, Glasgow, United Kingdom,
motcle:
Résumé:
Let P be an optimisation problem on a finite set of elements V, where an optimal solution of P is a subset of V. A d-transversal T is a subset of V such that the intersection between T and any optimal solution of P contains at least d elements of V. A d-transversal is optimum when its size is minimum.
Generally, the minimum transversal problem can be modelized as a bilevel 0-1 program which can be transformed in a 0-1 program with potentially an exponential number of constraints.
We propose a general framework to solve this problem when P is modelized by a 0-1 mathematical program.We test the efficiency of this approach for the case where P is the maximum stable set or the maximum matching problem. In these cases, P can be modelized as a 0-1 linear program. Our algorithm is based on a constraints generation method and use a 0-1 linear program solver. We present numerical results for both problems.
BibTeX
| @inproceedings { | |||
| CCP15a, | |||
| title | = | "{A general framework for finding d-transversals in graphs}", | |
| author | = | " G. Cotté and M.-C. Costa and C. Picouleau ", | |
| booktitle | = | "{EURO}", | |
| year | = | 2015, | |
| month | = | "July", | |
| pages | = | "1", | |
| address | = | "Glasgow, United Kingdom", | |
| } | |||
