Improved Bounds for the Token Distribution Problem

Abstract

The problem of packet routing on bounded degree networks is considered. An algorithm is presented that can route $n$ packets in $O$(log $n + K)$ time on a particular $n$-node expander-based network provided that no more than $K$ packets share the same source or destination.