A general framework for finding d-transversals in graphs
2015
Publication type:
Conference without proceedings
Conference:
EURO (Glasgow)
Abstract:
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:
@conference{Cot-Cos-Pic-2015, author={Grégoire Cotté and Marie-Christine Costa and Christophe Picouleau }, title={A general framework for finding d-transversals in graphs }, publisher={EURO (Glasgow) }, year={2015 }, }