Routing algorithms on a mesh-connected computer

The authors present two algorithms for the 1-1 routing problems on a mesh-connected computer. The first algorithm, with a queue size of 28, solves the 1-1 routing problem on an n×n mesh-connected computer in 2n+O(1) steps. This improves the previous result of queue size 75. The second algorithm solves the problem in 2n-2 steps with queue size 12t _s/s where t_s is the time for sorting an s×s mesh into a row major order for all s⩾1. This result improves the previous result of size 18.67 t_s/s. Both algorithms have important applications in reducing the hardware cost on a mesh-connected computer