Extended Fibonacci cubes
Extended Fibonacci cubes
复制标题
DOI：
10.1109/spdp.1995.530691
复制
发表时间：
1995-10
期刊：
影响因子：
--
通讯作者：
Jie Wu
中科院分区：
文献类型：
--
作者：
Jie Wu
斐波那契立方体 (FC) 是一种互连网络，拥有许多在网络设计和应用中非常重要的理想属性。然而，大多数斐波那契立方体（超过三分之二）都不是哈密顿量。在本文中，我们提出了一种称为扩展斐波那契立方体（EFC/sub 1/）的新网络拓扑，其基于与常规斐波那契序列相同的序列 F(i)=F(i-1)+F(i-2)，但具有不同的初始值。我们还提出了一系列具有偶数节点的扩展斐波那契立方体。该系列中的任何扩展斐波那契立方体（EFC/sub k/，带有 k/spl ges/1）都包含该系列中 EFC/sub k/ 之前的任何其他立方体的节点集。我们证明，任何扩展的斐波那契立方体几乎都保留了斐波那契立方体的所有所需属性。 EFC/sub k/'s 可以被认为是不完全超立方体的灵活版本，它消除了对节点数量的限制，从而使得构造任意大小的并行机成为可能。
The Fibonacci cube (FC) is an interconnection network that possesses many desirable properties that are important in network design and application. However, most Fibonacci cubes (more than two third of all) are not Hamiltonian. In this paper, we propose a new network topology called extended Fibonacci cube (EFC/sub 1/) based on the same sequence F(i)=F(i-1)+F(i-2) as the regular Fibonacci sequence but with different initial values. We also propose a series of extended Fibonacci cubes with even number of nodes. Any extended Fibonacci cube (EFC/sub k/, with k/spl ges/1) in the series contains the node set of any other cube that precedes EFC/sub k/ in the series. We show that any extended Fibonacci cube maintains virtually all the desirable properties of the Fibonacci cube. EFC/sub k/'s can be considered as flexible versions of incomplete hypercubes which eliminate the restriction on the number of nodes and thus makes it possible to construct parallel machines with arbitrary sizes.