Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes |
| |
Authors: | Wenjun Xiao Behrooz Parhami |
| |
Institution: | a Department of Computer Science, South China University of Technology, Guangzhou 510641, China b Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA 93106-9560, USA |
| |
Abstract: | In this paper, we extend known relationships between Cayley digraphs and their subgraphs and coset graphs with respect to subgroups to obtain a number of general results on homomorphism between them. Intuitively, our results correspond to synthesizing alternative, more economical, interconnection networks by reducing the number of dimensions and/or link density of existing networks via mapping and pruning. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes, including the derivation of provably correct shortest-path routing algorithms for such networks. |
| |
Keywords: | Cayley digraphs Cellular networks Coset graphs Diameter Distributed systems Homomorphism Interconnection networks Internode distance Parallel processing Routing |
本文献已被 ScienceDirect 等数据库收录! |
|