@inproceedings{29e4603c181046b482cbf52122aa6418,
title = "Derandomizing algorithms for routing and sorting on meshes",
abstract = "We describe a new technique that can be used to derandomize a number of randomized algorithms for routing and sorting on meshes. We demonstrate the power of this technique by deriving improved deterministic algorithms for a variety of routing and sorting problems. Our main results are an optimal algorithm for k-k routing on multi-dimensional meshes, a permutation routing algorithm with running time 2n+o(n) and queue size 5, and an optimal algorithm for 1-1 sorting.",
author = "Michael Kaufmann and Sibeyn, {Jop F.} and Torsten Suel",
year = "1994",
language = "English (US)",
isbn = "0898713293",
series = "Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms",
publisher = "Publ by ACM",
pages = "669--679",
booktitle = "Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms",
note = "Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-1994 Through 25-01-1994",
}