Lift-and-project ranks of the stable set polytope of joined a-perfect graphs

dc.creatorBianchi, S
dc.creatorEscalante, Mariana Silvina
dc.creatorMontelar, María Susana
dc.date.accessioned2018-07-23T17:24:13Z
dc.date.accessioned2018-11-06T14:40:06Z
dc.date.available2018-07-23T17:24:13Z
dc.date.available2018-11-06T14:40:06Z
dc.date.created2018-07-23T17:24:13Z
dc.date.issued2016-09
dc.identifierBianchi, S; Escalante, Mariana Silvina; Montelar, María Susana; Lift-and-project ranks of the stable set polytope of joined a-perfect graphs; Elsevier Science; Discrete Applied Mathematics; 210; 9-2016; 176-184
dc.identifier0166-218X
dc.identifierhttp://hdl.handle.net/11336/52835
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1888823
dc.description.abstractIn this paper we study lift-and-project polyhedral operators defined by Lovász and Schrijver and Balas, Ceria and Cornuéjols on the clique relaxation of the stable set polytope of webs. We compute the disjunctive rank of all webs and consequently of antiwebs. We also obtain the disjunctive rank of the antiweb constraints for which the complexity of the separation problem is still unknown. Finally, we use our results to provide bounds of the disjunctive rank of larger classes of graphs as joined a-perfect graphs, where near-bipartite graphs belong to.
dc.languageeng
dc.publisherElsevier Science
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/https://dx.doi.org/10.1016/j.dam.2015.11.001
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X15005272
dc.rightshttps://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.subjectLIFT-AND-PROJECT OPERATORS
dc.subjectPOLYHEDRAL COMBINATORICS
dc.subjectSTABLE SET POLYTOPE
dc.subjectWEBS
dc.titleLift-and-project ranks of the stable set polytope of joined a-perfect graphs
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución