Abstract
The existence and construction of cycles of various lengths in an interconnection network are important issues in efficiently executing ring-structured parallel algorithms in such a network. The hexagonal honeycomb mesh (HHM) is regarded as a promising candidate for interconnection networks. In this paper we address the problem of how to embed even-length cycles in an HHM. We prove that an HHM of order t≥3 admits a cycle of length l for each even number l such that l=6 or 10≤l≤6t 2−2. We also describe a systematic method for building these cycles.
Acknowledgements
The authors wish to express their gratitude to the anonymous referees for their constructive suggestions that have greatly improved the quality of this paper. This work is supported by Program for New Century Excellent Talent of Educational Ministry of China (NCET-05–0759), Doctorate Foundation of Educational Ministry of China (20050611001), and Natural Science Foundation of Chongqing CSTC (2006BB2231, 2005BB2191).