Artículo
Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphs
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
Licencia
Identificadores
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - 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