de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Towards Practical Permutation Routing on Meshes

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44745

Kaufmann,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45038

Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Sibeyn,  Jop F.
Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-AD4D-F
Zusammenfassung
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.