Lovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

dc.creatorBianchi, Maria Silvia
dc.creatorEscalante, Mariana Silvina
dc.creatorNasini, Graciela Leonor
dc.creatorTuncel, Levent
dc.date.accessioned2018-07-30T15:51:46Z
dc.date.accessioned2018-11-06T11:35:02Z
dc.date.available2018-07-30T15:51:46Z
dc.date.available2018-11-06T11:35:02Z
dc.date.created2018-07-30T15:51:46Z
dc.date.issued2017-03
dc.identifierBianchi, 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
dc.identifier0025-5610
dc.identifierhttp://hdl.handle.net/11336/53393
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1855174
dc.description.abstractWe 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.
dc.languageeng
dc.publisherSpringer
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/s10107-016-1035-1
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007/s10107-016-1035-1
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subjectINTEGER PROGRAMMING
dc.subjectLIFT-AND-PROJECT METHODS
dc.subjectSEMIDEFINITE PROGRAMMING
dc.subjectSTABLE SET PROBLEM
dc.titleLovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución