|
 
|
[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,
motcle:
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
BibTeX
| @inproceedings { | |||
| CLR03a, | |||
| 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)}", | |
| year | = | 2003, | |
| month | = | "January", | |
| note | = | "{note}", | |
| } | |||
