[CLR03a] Minimal multicut and maximal integer multiflow in rings

Conférence Internationale avec comité de lecture : ISMP'03, Copenhague, Danemark, (et ROADEF'03, Avignon), January 2003,
Résumé: This presentation deals, on the one hand, with the minimization of multicuts, and on the other hand, with the maximization of integral multiflows. A ring is a connected graph where all vertices have degree 2, thus a ring is also a planar graph. Several simplifications can be made before solving the minimal multicut and the maximal integer multiflow problems in rings. The main one is that a path without terminals, except for its endpoints, may be reduced to a single edge, which is the lowest weighted edge of the path. Moreover problems in bidirectional rings can be transformed in equivalent problems in directed rings by doubling the number of commodities. In fact, without loss of generality, one can assume that there is a source and/or a sink located at each vertex. We propose a polynomial algorithm solve the minimal multicut problem in ring networks. The algorithm is based on the enumeration of several minimum cuts associated with an arbitrary path , each one containing one different edge of the path These cuts are obtained by using an algorithm given for rooted trees: it is based on the duality relation existing between multicut and multiflow. We propose also a polynomial algorithm in O(n) to solve the maximal integer multiflow problem in rings with uniform capacities. This algorithm is based on the continuous solution of the problem. In such graphs, we show that the multicut problem admits an immediate solution. \section*{Bibliography} [1]S. Cosares and I. Saniee. An optimization problem related to balancing loads on SONET rings. Telecommunication Systems 3 (1994) 165-181. [2] M-C. Costa, L. L\'{e}tocart et F. Roupin (2003). A greedy algorithm for multicut and integral multiflow in rooted trees. {\it Oper. Res. Lett.}, 31, 21-27. [3] E. Dalhaus, D.S Johnson, C.H. Papadimitriou, P.D. Seymour et M. Yannakakis (1994). The complexity of multiway cuts. {\it SIAM J. Comput.}, 23, 864-894. [4] N. Garg, V.V. Vazirani et M. Yannakakis (1997). Primal-dual approximation algorithms for integral flow and multicut in trees. {\it Algorithmica} 18, 3-20. [5] P. Kubat, A. Shulman, R. Vachani et J. Ward (1996). Multicommodity flows in ring networks. {\it INFORMS J. Comput.} 8(3), 235-242. [6] L. L\'{e}tocart (2002). Probl\`{e}mes de multicoupes minimales et de multiflots maximaux en nombres entiers. Th\`{e}se de Doctorat, CNAM.

Commentaires: note

Collaboration: LIPN


@inproceedings {
title="{Minimal multicut and maximal integer multiflow in rings}",
author=" M.-C. Costa and L. Létocart and F. Roupin ",
booktitle="{ISMP'03, Copenhague, Danemark, (et ROADEF'03, Avignon)}",