Carleton University
Technical Report TR-96-19
July 1996
Many-to-One Packet Routing via Matchings
Danny Krizanc & Louxin Zhang
Abstract
In this paper we study the packet routing problem under the matching model proposed by Alon, Chung and Graham \cite{ACG94}. We extend the model to allow more than one packet per origin and destination node. We give tight bounds for the many-to-one routing number for complete graphs, complete bipartite graphs and linear arrays. We also present an efficient algorithm for many-to-one routing on an trees (and therefore any graph).Finally, we give bounds for routing arbitrary relations in this model.