@inproceedings{ddf698be905c4fb3b20df437cc512ed5,
title = "Routing on meshes in optimum time and with really small queues",
abstract = "We consider permutation routing problems on 2D and 3D mesh-connected computers with side length n. Our main result is a deterministic online algorithm routing on 2D meshes, operating in worst-case time T = 2n + O(1) and with queue size Q = 3. We also develop offline routing algorithms with performance bounds T = 2n - 1 and Q = 2 for 2D meshes, and T = 3n - 2 and Q = 4 for 3D meshes. We also show that is it possible to route most of the permutations on 2D meshes offline in time T = 2n - 2 with Q = 1.",
author = "Chlebus, {Bogdan S.} and Sibeyn, {Jop F.}",
year = "2003",
month = jan,
day = "1",
doi = "10.1109/IPDPS.2003.1213148",
language = "English (US)",
series = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003",
note = "International Parallel and Distributed Processing Symposium, IPDPS 2003 ; Conference date: 22-04-2003 Through 26-04-2003",
}