Invited Session Fri.3.H 3004

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

Cluster 2: Combinatorial optimization [...]

Packing, covering and domination II

 

Chair: Annegret K. Wagler

 

 

Friday, 15:15 - 15:40 h, Room: H 3004, Talk 1

Arnaud Pecher
On the theta number of powers of cycle graphs

Coauthors: Christine Bachoc, Alain Thiery

 

Abstract:
A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 1981).
We give a closed formula for Lovász's theta number of the powers of
cycle graphs Ckd-1 and of their complements, the circular complete graphs Kk/d. As a consequence, we establish that the circular-chromatic number of a circular-perfect graph is computable in
polynomial time, which extends the above result from the chromatic number to the circular-chromatic number, and from perfect graphs to the superclass of circular-perfect graphs.

 

 

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

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

Coauthors: Mariana S. Escalante, Maria S. Montelar

 

Abstract:
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.

 

 

Friday, 16:15 - 16:40 h, Room: H 3004, Talk 3

Luis Miguel Torres
On the Chvátal-closure of the fractional set covering polyhedron of circulant matrices

Coauthor: Paola Tolomei

 

Abstract:
The set covering polyhedron Q*(Cnk) related to circulant 0,1-matrices has been the object of several recent studies. It has been conjectured that the Chvátal-rank of its fractional relaxation Q(Cnk) is equal to 1. In 2009, Argiroffo and Bianchi characterized all vertices of Q(Cnk). Building upon their characterization, we investigate the first Chvátal-closure of this polyhedron. Our aim is to obtain a complete linear description, by considering the integral generating sets of the cones spanned by the normal vectors of the facets containing each vertex of Q(Cnk). In this talk we present the results obtained so far for some classes of vertices. In particular, our construction yields a counterexample to a conjecture that all facets of Q*(Cnk) are given by boolean, nonnegative, and so-called minor inequalities having only coefficients in {1,2}. At the same time, we motivate why a weaker version of this conjecture might still hold.

 

  The majority of financial loan companies provide the service of getting Payday Loans North Carolina for U.S. citizens. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.