Artículo
On the facets of lift-and-project relaxations under graph operations
Fecha de publicación:
02/2014
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
We study the behavior of lift-and-project procedures for solving combinatorial optimization problems as described by Lovász and Schrijver (1991) [6] in the context of the stable set 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 relaxations obtained 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 the star subdivision, the stretching of a node and a new operation defined herein called the clique subdivision of an edge
Palabras clave:
Operations in Graphs
,
Lift-And-Project Operators
,
Stable Set
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos(IMAL)
Articulos de INST.DE MATEMATICA APLICADA "LITORAL"
Articulos de INST.DE MATEMATICA APLICADA "LITORAL"
Citación
Aguilera, Néstor Edgardo; Escalante, Mariana Silvina; Fekete, Pablo Gabriel; On the facets of lift-and-project relaxations under graph operations; Elsevier Science; Discrete Applied Mathematics; 164; 2; 2-2014; 360-372
Compartir
Altmétricas