Optimal many-to-one routing on the mesh with constant queues

We present randomized and deterministic algorithms for many-to-one packet routing on an n-node two-dimensional mesh under the store-and-forward model. We consider the general instance of many-to-one routing where each node is the source (resp., destination) of ℓ (resp., k) packets, for arbitrary values of ℓ and k. All our algorithms run in optimal O(ℓkn) time and use queues of only constant size at each node to store packets in transit. The randomized algorithms, however, are simpler to implement. Our result closes a gap in the literature, where time-optimal algorithms using constant-size queues were known only for the special cases ℓ=1 and ℓ=k.