Derandomizing algorithms for routing and sorting on meshes

Michael Kaufmann, Jop F. Sibeyn, Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
    PublisherPubl by ACM
    Pages669-679
    Number of pages11
    ISBN (Print)0898713293
    StatePublished - 1994
    EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
    Duration: Jan 23 1994Jan 25 1994

    Publication series

    NameProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

    Other

    OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
    CityArlington, VA, USA
    Period1/23/941/25/94

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Derandomizing algorithms for routing and sorting on meshes'. Together they form a unique fingerprint.

  • Cite this

    Kaufmann, M., Sibeyn, J. F., & Suel, T. (1994). Derandomizing algorithms for routing and sorting on meshes. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (pp. 669-679). (Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms). Publ by ACM.