Embedding K-ary Complete Trees into Hypercubes

In this paper, dilated embedding and precise embedding of K-ary complete trees into hypercubes are studied. For dilated embedding, a nearly optimal algorithm is proposed which embeds a K-ary complete tree of height h, T K ( h), into an ( h − 1)[log K] + [log ( K + 2)]-dimensional hypercube with dila...

Full description

Saved in:
Bibliographic Details
Published in:Journal of parallel and distributed computing 1995, Vol.24 (1), p.100-106
Main Authors: Shen, X.J., Hu, Q., Liang, W.F.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Information retrieval. Graph
Theoretical computing
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, dilated embedding and precise embedding of K-ary complete trees into hypercubes are studied. For dilated embedding, a nearly optimal algorithm is proposed which embeds a K-ary complete tree of height h, T K ( h), into an ( h − 1)[log K] + [log ( K + 2)]-dimensional hypercube with dilation Max{2, φ( K), φ( K + 2)}. φ( x) = min{ λ: Σ λ i= 0 C i d ≥ x and d = [log x]}. It is clear that [([log x] + 1)/2] ≤ φ( x) ≤ [log x], for x ≥ 3.) For precise embedding, we show a ( K − 1) h + 1-dimensional hypercube is large enough to contain T K ( h) as its subgraph, K ≥ 3.
ISSN:0743-7315
1096-0848
DOI:10.1006/jpdc.1995.1010