Contributed Session Thu.2.H 3004

Thursday, 13:15 - 14:45 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Cycles in graphs


Chair: Peter Recht



Thursday, 13:15 - 13:40 h, Room: H 3004, Talk 1

Peter Recht
A "min-max-theorem'' for the cycle packing problem in Eulerian graphs

Coauthor: Eva-Maria Sprengel


This lecture deals with the problem to determine a set \  Z*= {C1, C2, … , C ν (G) } of edge-disjoint cycles of maximum cardinality ν (G) in a graph G=(V,E). The problem is tackled by considering special subgraphs: \ for a vertex v ∈ V, let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). \ In general, maximal local traces are not uniquely defined but their packing numbers ν (T(v)) are. \ We prove that if G is is Eulerian every maximum edge-disjoint cycle packing Z* of G induces maximum local traces T(v) at v for every v ∈ V. In the opposite, if the total size v ∈ V |E(T(v)| is minimal then the set of induced edge-disjoint cycles in G must be maximum. \ The determination of such a maximal trace leads to a multi-commodity flow-problem with quadratic objective function.



Thursday, 13:45 - 14:10 h, Room: H 3004, Talk 2

Eva-Maria Sprengel
An optimal cycle packing for generalized Petersen graphs P(n,k) with k even

Coauthor: Peter Recht


For an undirected graph G=(V,E) a maximum cycle packing is a collection of pairwise edge-disjoint cycles. The maximum cardinality of such a packing is denoted as the cycle packing number ν (G).
In general the determination of a maximum cycle packing and the cycle packing number, respectively, is NP-hard.
In this lecture we consider the family of generalized Petersen graphs P(n,k) with k even. We give a lower and an upper bound on the cycle packing number and outline the structure of one optimal cycle packing of such graphs.



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

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.


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.