Near-optimal embeddings of trees into Fibonacci cubes
Bin Gong, Si Zheng · 2002
The Fibonacci cube network was proposed recently as an alternative to the hypercube network. In this paper, we consider the problems of simulating tree and X-tree structures by the Fibonacci cube. Such problems can be characterized as network embedding. There is a big gap between the hypercube and the Fibonacci cube with respect to the availability of routing and embedding results. We present near-optimal embedding results, which show that the Fibonacci cube can simulate trees and X-trees almost as efficiently as the hypercube, even though the Fibonacci cube is a network much sparser than the hypercube.