INVESTIGADORES
ESCALANTE Mariana Silvina
congresos y reuniones científicas
Título:
Characterizing N+-perfect line graphs
Autor/es:
ESCALANTE, MARIANA SILVINA; NASINI, GRACIELA LEONOR; WAGLER, ANNEGRET
Lugar:
Montevideo
Reunión:
Workshop; EURO ALIO Workshop on Applied and Combinatorial Optimization; 2014
Institución organizadora:
ALIO-EURO IFORS
Resumen:
The subject of this contribution is the study of the
Lov´asz-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 the
PSD-operator 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 graphs are cliques
and odd holes.