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


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.


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


  Today, Ohio Payday Loans are legitimate, but there are illegal transactions that are still on the rise. But at the same time, it acts only with sexual arousal. Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.