Thursday, 14:15 - 14:40 h, Room: H 3004


Lamia Aoudia
4-cycle polytope on a graph

Coauthor: Meziane Aider


The aim of this work is to give a convex hull of 4-cycle on a wider class of complete bipartite graphs.\
Given a bipartite graph Kn,m, where |{V1}|=n and
|{V1}|=m, E=V1 × V2 and a weight function w: E → R, The minimum weighted 4-cycle problem consist on finding a 4-cycle C ⊂ E such hat e ∈ Cwe is minimum. This problem can easily be solved in polynomial time by complete enumeration of the the 4-cycles of G. For each 4-cycle C, let XC denote the incidence vector of C defined by: XC (e) = 1 and XC =0 if e\notin C. The 4-cycle polytope PC4 n , m is the convex hull of the incidence vectors of the 4-cycles of Kn,m, i.e. PC4 n , m = convex hull {XC ∈ {0,1}: C is a 4-cycle of G }
The minimum weighted 4-cycle problem is clearly equivalent to the linear program min {wx :  x ∈ PC4n,n }.
We are mainly interested by the facial tructure of PC4 n,m. Thus, we enumerate some inequalities defining facets of PC4 n, n.


Talk 3 of the contributed session Thu.2.H 3004
"Cycles in graphs" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.