Mostrar el registro sencillo del ítem

dc.contributor.author
Escalante, Mariana Silvina  
dc.contributor.author
Nasini, Graciela Leonor  
dc.contributor.author
Wagler, Annegret Katrin  
dc.date.available
2018-07-17T19:50:00Z  
dc.date.issued
2017-01  
dc.identifier.citation
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  
dc.identifier.issn
0969-6016  
dc.identifier.uri
http://hdl.handle.net/11336/52511  
dc.description.abstract
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.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Wiley  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
N+-Perfect Graphs  
dc.subject
Line Graphs  
dc.subject
Psd Relaxation  
dc.subject
Stable Set Polytope  
dc.subject.classification
Matemática Pura  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Characterizing N+-perfect line graphs  
dc.type
info:eu-repo/semantics/article  
dc.type
info:ar-repo/semantics/artículo  
dc.type
info:eu-repo/semantics/publishedVersion  
dc.date.updated
2018-07-17T13:57:10Z  
dc.journal.volume
24  
dc.journal.number
1-2  
dc.journal.pagination
325-337  
dc.journal.pais
Estados Unidos  
dc.journal.ciudad
Hoboken  
dc.description.fil
Fil: Escalante, Mariana Silvina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina  
dc.description.fil
Fil: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina  
dc.description.fil
Fil: Wagler, Annegret Katrin. Universite Blaise Pascal; Francia. Centre National de la Recherche Scientifique; Francia  
dc.journal.title
International Transactions in Operational Research  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1111/itor.12275  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12275