The purpose of this note is to effectively solve routing
(multicommodity flow) problems specialized to ring networks (circles). This
note describes an O(n^{2}) 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(n^{2}). Instead we start with an
algorithm of Schrijver, Seymour and Winkler developed for
rings. They claimed O(n^{4}) 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(n^{2}).
Bibtex entry:
@techreport{egres-05-10,
AUTHOR | = | {Kir{\'a}ly, Zolt{\'a}n}, |
TITLE | = | {An $O(n^2)$ algorithm for ring routing}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2005}, |
NUMBER | = | {TR-2005-10} |