Title

An Optimal Embedding of Double-Rooted Binary Trees in Hypercubes

Document Type

Report

Date

2-1991

Keywords

Hypercubes, Binary trees

Language

English

Disciplines

Computer Sciences

Description/Abstract

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.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-91-08

Source

local

This document is currently not available here.

Share

COinS