IMAL 13325
INSTITUTO DE MATEMATICA APLICADA DEL LITORAL "DRA. ELEONOR HARBOURE"
Unidad Ejecutora - UE
artículos
Título:
On the facets of lift-and-project relaxations under graph operations
Autor/es:
AGUILERA, NESTOR EDGARDO; ESCALANTE, MARIANA SILVINA; FEKETE, PABLO GABRIEL
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2012
ISSN:
0166-218X
Resumen:
We study the behavior of lift-and-project procedures for solving combinatorial optimizationproblems as described by Lovász and Schrijver (1991) [6] in the context of the stableset problem on graphs. Following the work of Wolsey (1976) [10], Lipták and Lovász (2001)[4] and Lipták and Tunçel (2003) [5], we investigate how to generate facets of the relaxationsobtained by these procedures from facets of the relaxations of the original graph,after applying fundamental graph operations. We show our findings for the odd and thestar subdivision, the stretching of a node and a new operation defined herein called theclique subdivision of an edge
