Artículo
Characterizing N+-perfect line graphs
Fecha de publicación:
01/2017
Editorial:
Wiley
Revista:
International Transactions in Operational Research
ISSN:
0969-6016
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
The aim of this paper is to study the Lovász-Schrijver PSD operator N+ applied to the edge relaxation of the stable set polytope of a graph. We are particularly interested in the problem of characterizing graphs for which N+ generates the stable set polytope in one step, called N+ -perfect graphs. It is conjectured that the only N+ -perfect graphs are those whose stable set polytope is described by inequalities with near-bipartite support. So far, this conjecture has been proved for near-perfect graphs, fs-perfect graphs, and webs. Here, we verify it for line graphs, by proving that in an N+ -perfect line graph the only facet-defining subgraphs are cliques and odd holes.
Palabras clave:
N+-Perfect Graphs
,
Line Graphs
,
Psd Relaxation
,
Stable Set Polytope
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Citación
Escalante, Mariana Silvina; Nasini, Graciela Leonor; Wagler, Annegret Katrin; Characterizing N+-perfect line graphs; Wiley; International Transactions in Operational Research; 24; 1-2; 1-2017; 325-337
Compartir
Altmétricas