Artículo

On the facets of the lift-and-project relaxations of graph subdivisions

Aguilera, Néstor EdgardoIcon ; Escalante, Mariana SilvinaIcon ; Fekete, Pablo GabrielIcon
Fecha de publicación: 08/2011
Editorial: Elsevier
Revista: Electronic Notes in Discrete Mathematics
ISSN: 1571-0653
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), in the context of the stable set problem on graphs. Following the work of Wolsey (1976), 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 subdivision of an edge and its generalization, the stretching of a vertex operation.
Palabras clave: Graph Subdivision , Lift-And-Project , Stable Set Problem
 
Archivos asociados
Thumbnail
 
Tamaño: 175.0Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/68103
DOI: http://dx.doi.org/10.1016/j.endm.2011.05.035
URL: https://www.sciencedirect.com/science/article/pii/S1571065311000369
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos(IMAL)
Articulos de INST.DE MATEMATICA APLICADA "LITORAL"
Citación
Aguilera, Néstor Edgardo; Escalante, Mariana Silvina; Fekete, Pablo Gabriel; On the facets of the lift-and-project relaxations of graph subdivisions; Elsevier; Electronic Notes in Discrete Mathematics; 37; C; 8-2011; 201-206
Compartir
Altmétricas