%0 Journal Article %1 upfal92 %A Upfal, Eli %C New York, NY, USA %D 1992 %I ACM %J J. ACM %K algorithm routing sorting.network %N 1 %P 55--70 %R 10.1145/147508.147517 %T An $O(Log N)$ Deterministic Packet-routing Scheme %V 39 %X A deterministic O(log N)-time algorithm for the problem of routing an aribitrary permutation on an N-processor bounded-degree network with bounded buffers is presented.Unlike all previous deterministic solutions to this problem, our routing scheme does not reduce the routing problem to sorting and does not use the sorting network of Ajtai, et al. 1. Consequently, the constant in the run time of our routing scheme is substantially smaller, and the network topology is significantly simpler.

@article{upfal92, abstract = {A deterministic O(log N)-time algorithm for the problem of routing an aribitrary permutation on an N-processor bounded-degree network with bounded buffers is presented.Unlike all previous deterministic solutions to this problem, our routing scheme does not reduce the routing problem to sorting and does not use the sorting network of Ajtai, et al. [1]. Consequently, the constant in the run time of our routing scheme is substantially smaller, and the network topology is significantly simpler.}, acmid = {147517}, added-at = {2016-10-30T11:55:12.000+0100}, address = {New York, NY, USA}, author = {Upfal, Eli}, biburl = {https://www.bibsonomy.org/bibtex/2a1ec7a89b2b61d077eed674485b2072f/ytyoun}, doi = {10.1145/147508.147517}, interhash = {caf16730bdadecd2ea35960440e14d16}, intrahash = {a1ec7a89b2b61d077eed674485b2072f}, issn = {0004-5411}, issue_date = {Jan. 1992}, journal = {J. ACM}, keywords = {algorithm routing sorting.network}, month = jan, number = 1, numpages = {16}, pages = {55--70}, publisher = {ACM}, timestamp = {2016-11-06T09:06:40.000+0100}, title = {An $O(Log N)$ Deterministic Packet-routing Scheme}, volume = 39, year = 1992 }