The purpose of this note is to effectively solve routing
(multicommodity flow) problems specialized to ring networks (circles). This
note describes an O(n2) algorithm for solving ring routing. The solution
is always half-integer (if the input is integer), and it is integer if the
problem is Eulerian. We show a simple modification that solves the integral
routing problem also for the non-Eulerian case.
A lot of nice algorithms are known for similar, but more general problems. However not known specialization of
these algorithms to rings runs in O(n2). Instead we start with an
algorithm of Schrijver, Seymour and Winkler developed for
rings. They claimed O(n4) running time. Here we show that with some
modification of their algorithm and with a careful implementation the
running time can be decreased to O(n2).
Bibtex entry:
AUTHOR | = | {Kir{\'a}ly, Zolt{\'a}n}, |
TITLE | = | {An $O(n^2)$ algorithm for ring routing}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2005}, |
NUMBER | = | {TR-2005-10} |