Abstract
A “minimal routings” scheme is presented that yields a shortest path between any source and destination node in a triangular (or “hexavalent”) grid. The simplicity of the protocol results from a preliminary statement of a hexagonal coordinate system that perfectly fits the symmetries of the grid. A shortest path routing is first stated for the infinite grid and normalized afterwards for a family of Cayley graphs — namely the arrowhead and the diamond — organized as tori.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M.S. Chen, K.G. Shin, D.D. Kandlur: Addressing, routing, and broadcasting in hexagonal mesh multiprocessors. IEEE Trans. Comp. 39 (1) (1990) 10–18
W.J. Dally, C.L. Seitz: The torus routing chip. Distributed Computing 1 (1986) 187–196
A. Davis: Mayfly — a general-purpose, scalable, parallel processing architecture. J. LISP and Symbolic Computation 5 (1992) 7–47
A.L. Davis, S.V. Robison: The architecture of the FAIM-1 symbolic multiprocessing system. Proc. 9-th Int. Joint. Conf. on Artificial Intelligence (1985) 32–38
D. Désérable: Broadcasting in the arrowhead torus. Parallel Processing, Lecture Notes in Computer Sciences 854, Springer-Verlag (1994) 808–819
D. Désérable: A family of Cayley graphs on the hexavalent grid (to appear in Discrete Applied Math.)
A. Rosenfeld, P. Pfaltz: Distance functions on digital pictures. Pattern Recognition 1 (1968) 33–61
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Désérable, D. (1997). Minimal routing in the triangular grid and in a family of related tori. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002736
Download citation
DOI: https://doi.org/10.1007/BFb0002736
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive