Friday, 15:45 - 16:10 h, Room: H 3004


Silvia Bianchi
The disjunctive rank of the stable set polytope of web graphs

Coauthors: Mariana S. Escalante, Maria S. Montelar


We consider the behavior of the disjunctive operator defined by Balas, Ceria and Cornuéjols, over the clique relaxation of the stable set problem on webs. The disjunctive rank of a graph is the minimum number of steps of this procedure needed to obtain the convex hull of integer solutions in it. In this work we obtain the disjunctive rank of all webs, when starting from the clique relaxation. We find that almost every web Wnk attain the upper bound of its disjunctive rank,i.e. k, except for those of the form W3k+rk with r=0 or r=1, that requires k-2 or k-1 steps, respectively.
Our results allow us to obtain bounds for the disjunctive rank of a larger class of graphs such as quasi-line graphs and their complements, the near-bipartite graphs.


Talk 2 of the invited session Fri.3.H 3004
"Packing, covering and domination II" [...]
Cluster 2
"Combinatorial optimization" [...]


  Illinois Payday Loans should not be obtained by people who do not have the capacity to repay the lenders. Since its introduction in the market buying Buy Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.