English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Towards Practical Permutation Routing on Meshes

Kaufmann, M., Meyer, U., & Sibeyn, J. F. (1994). Towards Practical Permutation Routing on Meshes. In Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing (pp. 656-663). Los Alamitos, USA: IEEE.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kaufmann, Michael1, Author           
Meyer, Ulrich1, Author           
Sibeyn, Jop F.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Max Planck Society, ou_persistent13              

Content

show
hide
Free keywords: -
 Abstract: We consider the permutation routing problem on two-dimensional n x n meshes. To be practical, a routing algorithm is required to ensure very small queue sizes Q, and very low running time T, not only asymptotically but particularly also for the practically important n up to 1000. With a technique inspired by a scheme of Kaklamanis/Krizanc/Rao, we obtain a near-optimal result: T = 2 n + O(1) with Q = 2. Although Q is very attractive now, the lower order terms in T make this algorithm highly impractical. Therefore we present simple schemes which are asymptotically slower, but have T around 3 n for all n and Q between 2 and 8.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-021994
 Publication Status: Issued
 Pages: -
 Publishing info: Los Alamitos, USA : IEEE
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 517773
Other: Local-ID: C1256428004B93B8-7A0181422E9E98C9C12564AC00344689-Kaufmann-Meyer-Sibeyn94
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Dallas, Texas
Start-/End Date: 1994

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Los Alamitos, USA : IEEE
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 656 - 663 Identifier: ISBN: 0-8186-6427-4