Article ID Journal Published Year Pages File Type
419214 Discrete Applied Mathematics 2016 9 Pages PDF
Abstract

In 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 aa-perfect graphs, where near-bipartite graphs belong to.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,