Deterministic Permutation Routing on Meshes

Jop F. Sibeyn, Bogdan S. Chlebus, Michael Kaufmann

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


New deterministic algorithms for routing permutations on two-dimensional meshes are developed. On an n × n array, one algorithm runs in the optimal 2 · n - 2 steps, with maximum queue length 32. Another algorithm runs in near-optimal time, 2 · n + script O sign(1) steps, with a maximum queue length of only 12.

Original languageEnglish (US)
Pages (from-to)111-141
Number of pages31
JournalJournal of Algorithms
Issue number1
StatePublished - Jan 1997
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Deterministic Permutation Routing on Meshes'. Together they form a unique fingerprint.

Cite this