The Minimum Weighted Cycle Problem: Polytopes and Algorithms

Session : GR / Graphes
Jeudi 11 février 15:00 - 16:40 Salle : RP13
Mourad Baïou, Laurent Beaudou, Vincent Limouzy et Henri Perret Du Cray

In this work, we study the minimum weighted cycle problem. We present a compact linear relaxation of the problem. We show that this formulation describe the associated polytope when the graph is series-parallel. In addition, we give a linear time algorithm to find a cycle of minimum weight in series-parallel graphs and we present a variant of this problem when the cycle is of fixed size.

Mots clés : cycle, series-parallel, polytope, compact formulation