An Optimal Embedding of Double-Rooted Binary Trees in Hypercubes
Hypercubes, Binary trees
From the hardware and software points of view, the double-rooted binary tree (DRBT) structure is very useful for many computer applications. A DRBT machine was proposed in [BeKu79]. It was designed to solve a large class of searching problems and is ideally suited for implementation in VLSI. It was also used as a database machine which can efficiently process many database operations such as selection, join, deletion, insertion, searching, etc. [Su88]. From the algorithm point of view, the divide-and-conquer algorithms can also be represented by DRBTs. In this paper, we present a mapping algorithm to embed DRBTs in hypercubes. Our algorithm can embed a DRBT in a hypercube with unit dilation and unit expansion.
Chung, Yeh-Ching and Ranka, Sanjay, "An Optimal Embedding of Double-Rooted Binary Trees in Hypercubes" (1991). Electrical Engineering and Computer Science Technical Reports. 121.