Characterizing N+-perfect line graphs | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Universite Blaise Pascal | |
| dc.conicet.organizacion | Centre National de la Recherche Scientifique | |
| dc.contributor.author | Escalante, Mariana Silvina | |
| dc.contributor.author | Nasini, Graciela Leonor | |
| dc.contributor.author | Wagler, Annegret Katrin | |
| dc.date.issued | 2017-01 | |
| 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. | es |
| 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.format | application/pdf | es |
| 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 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0969-6016 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/52511 | |
| dc.journal.ciudad | Hoboken | es |
| dc.journal.number | 1-2 | es |
| dc.journal.pagination | 325-337 | es |
| dc.journal.pais | Estados Unidos | es |
| dc.journal.title | International Transactions in Operational Research | es |
| dc.journal.volume | 24 | es |
| dc.language.iso | eng | es |
| dc.publisher | Wiley | es |
| 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 | |
| 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 | es |
| dc.subject | Line Graphs | es |
| dc.subject | Psd Relaxation | es |
| dc.subject | Stable Set Polytope | es |
| dc.subject.classification | Matemática Pura | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Characterizing N+-perfect line graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.4ac9d644-ce68-462b-81a2-8754b05a2ae9_A.pdf
- Tamaño:
- 281.97 KB
- Formato:
- Adobe Portable Document Format