Enhanced Fibonacci Cubes
Haifeng Qian · The Computer Journal · 1996
We propose the enhanced Fibonacci cube (EFC) structure for parallel systems. It is defined based on the sequence Fn = 2Fn−2+2Fn−4. We show that the enhanced Fibonacci cube contains the Fibonacci cube (FC) as a subgraph and maintains virtually all the desirable properties of the Fibonacci cube. In addition, it is a Hamiltonian graph. We can embed complete binary trees into enhanced Fibonacci cubes with dilation one and with a relatively small expansion. We also propose a series of enhanced Fibonacci cubes EFC(k), where k is a series number. Each EFC(k) contains an FC of the same order as a subcube. Moreover, each EFC(k) in the series contains any other cube that precedes it as subcubes and the last one in the series is a hypercube of the corresponding order. This series of EFC(k)s provides us with more options for selecting cubes with various sizes. Because EFC is a subgraph of the hypercube, it may find applications in fault-tolerant computing for degraded hypercube computer systems. As an application of EFC, we show that the parallel prefix sum computation can be efficiently implemented on enhanced Fibonacci cubes.