Artículo

Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphs

Bianchi, Silvia M.; Escalante, Mariana SilvinaIcon ; Nasini, Graciela LeonorIcon ; Wagler, Annegret K.
Fecha de publicación: 06/2023
Editorial: Elsevier Science
Revista: Discrete Applied Mathematics
ISSN: 0166-218X
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

The subject of this work is the study of LS+-perfect graphs defined as those graphs G for which the stable set polytope STAB(G) is achieved in one iteration of Lovász–Schrijver PSD-operator LS+, applied to its edge relaxation ESTAB(G). The recently formulated LS+-Perfect Graph Conjecture aims at a characterization of this family of graphs, through the structure of the facet defining inequalities of the stable set polytope. The main contribution of this work is to verify it for the well-studied class of claw-free graphs.
Palabras clave: CLAW-FREE GRAPHS , SEMIDEFINITE RELAXATION , STABLE SET PROBLEM
 
Archivos asociados
Tamaño: 704.6Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/restrictedAccess 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/223256
DOI: http://dx.doi.org/10.1016/j.dam.2023.01.012
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Citación
Bianchi, Silvia M.; Escalante, Mariana Silvina; Nasini, Graciela Leonor; Wagler, Annegret K.; Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphs; Elsevier Science; Discrete Applied Mathematics; 332; 6-2023; 70-86
Compartir
Altmétricas