An O(n2) algorithm for ring routing

Zoltán Király


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-10}

Last modification: 10.9.2021. Please email your comments to Tamás Király!