A Fibonacci string is a length ii binary string containing no two consecutive 1 s. Fibonacci cubes (FC), Extended Fibonacci cubes (ELC) and Lucas cubes (LC) are subgraphs of hvpercube defined in terms of Fibonacci strings. All these cubes were introduced in the last ten years as models for interconnection networks and shown that their network topology posseses many interesting properties that are important in parallel processor network design and parallel applications. In this paper, we propose a new family of Fibonacci-like cube, namely Extended Lucas Cube (ELC). We address the following network simulation problem : Given a linear array, a ring or a two-dimensional mesh; how can its nodes be assigned to ELC nodes so as to keep their adjacent nodes near each other in ELC ?. We first show a simple fact that there is a Hamiltonian path and cycle in any ELC. We prove that any linear array and ring network can be embedded into its corresponding optimum ELC (the smallest ELC with at least the number of nodes in the ring) with dilation 1, which is optimum for most cases. Then, we describe dilation 1 embeddings of a class of meshes into their corresponding optimum ELC. udKeywords: (Extended) Fibonacci cube, Extended Lucas cube, Fibonacci number, Hamiltonian path, Hamiltonian cycle, linear array, ring , mesh, networkud
展开▼
机译：Fibonacci字符串是长度ii的二进制字符串，不包含两个连续的1 s。 Fibonacci多维数据集（FC），扩展Fibonacci多维数据集（ELC）和Lucas多维数据集（LC）是根据Fibonacci字符串定义的hvpercube的子图。在过去的十年中，所有这些多维数据集都是作为互连网络的模型引入的，表明它们的网络拓扑具有许多有趣的属性，这些属性在并行处理器网络设计和并行应用程序中很重要。在本文中，我们提出了一个类似斐波那契立方体的新家族，即扩展卢卡斯立方体（ELC）。我们解决以下网络仿真问题：给定线性阵列，环形或二维网格；如何将其节点分配给ELC节点，以使它们的相邻节点在ELC中彼此靠近？我们首先显示一个简单的事实，即任何ELC中都有哈密顿路径和循环。我们证明，任何线性阵列和环网都可以通过扩张1嵌入其相应的最佳ELC（最小的ELC，至少具有环中节点数），这在大多数情况下都是最佳的。然后，我们将一类网格的膨胀1嵌入描述为其相应的最佳ELC。 ud关键字：（扩展的）斐波那契立方体，扩展的卢卡斯立方体，斐波那契数，哈密顿路径，哈密顿循环，线性阵列，环，网格，网络 ud
展开▼
