Lovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | University of Waterloo | |
| dc.contributor.author | Bianchi, Maria Silvia | |
| dc.contributor.author | Escalante, Mariana Silvina | |
| dc.contributor.author | Nasini, Graciela Leonor | |
| dc.contributor.author | Tuncel, Levent | |
| dc.date.issued | 2017-03 | |
| dc.description.abstract | We study the Lovász–Schrijver lift-and-project operator (LS +) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the LS +-operator generates the stable set polytope in one step has been open since 1990. We call these graphs LS +-perfect. In the current contribution, we pursue a full combinatorial characterization of LS +-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among LS +-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs. | es |
| dc.description.fil | Fil: Bianchi, Maria Silvia. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina | |
| dc.description.fil | Fil: Escalante, Mariana Silvina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina | |
| dc.description.fil | Fil: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina | |
| dc.description.fil | Fil: Tuncel, Levent. University of Waterloo; Canadá | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bianchi, Maria Silvia; Escalante, Mariana Silvina; Nasini, Graciela Leonor; Tuncel, Levent; Lovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs; Springer; Mathematical Programming; 162; 1-2; 3-2017; 201-223 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0025-5610 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/53393 | |
| dc.journal.ciudad | Berlín | es |
| dc.journal.number | 1-2 | es |
| dc.journal.pagination | 201-223 | es |
| dc.journal.pais | Alemania | es |
| dc.journal.title | Mathematical Programming | es |
| dc.journal.volume | 162 | es |
| dc.language.iso | eng | es |
| dc.publisher | Springer | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/s10107-016-1035-1 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007/s10107-016-1035-1 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Integer Programming | es |
| dc.subject | Lift-And-Project Methods | es |
| dc.subject | Semidefinite Programming | es |
| dc.subject | Stable Set Problem | es |
| dc.subject.classification | Matemática Pura | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Lovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite 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.26b43720-d589-41bb-954a-25f5ffcfec5f_X.pdf
- Tamaño:
- 415.49 KB
- Formato:
- Adobe Portable Document Format
- Descripción: