Embedding of meshes in Möbius cubes

详细信息	查看全文 | 推荐本文 |

• 作者：Chang-Hsiung Tsai
• 关键词：M&#xf6 ; bius cubes ; Mesh embedding ; Dilation ; Expansion ; Interconnection network
• 刊名：Theoretical Computer Science
• 出版年：2008
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：23 July 2008
• 卷：401
• 期：1-3
• 页码：181-190
• 文件大小：437 K

摘要

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. Möbius cubes form a class of hypercube variants that give better performance with the same number of edges and vertices. In this paper, we consider embedding of meshes in Möbius cubes. The main results obtained in this paper are: (1) For n≥1, there exists a f16381" title="Click to view the MathML source" alt="Click to view the MathML source">2×2ⁿ⁻¹ mesh that can be embedded in the n-dimensional Möbius cube with dilation 1 and expansion 1. (2) For n≥4, there exists a 4×2ⁿ⁻² mesh that can be embedded in the f1942a9654" title="Click to view the MathML source" alt="Click to view the MathML source">n-dimensional Möbius cube with dilation 2 and expansion 1. (3) For n≥4, there are two disjoint 4×2ⁿ⁻³ meshes that can be embedded in the 0-type n-dimensional Möbius cube with dilation 1. (4) For n≥4, there are two disjoint 4×2ⁿ⁻³ meshes that can be embedded in the 1-type f1555da771" title="Click to view the MathML source" alt="Click to view the MathML source">n-dimensional Möbius cube with dilation 2. Results of (1) and (3) are optimal in the sense that the dilations of the embeddings are 1.