Embedding K-ary Complete Trees into Hypercubes

X. J. Shen; Q. Hu; W. F. Liang

doi:10.1006/jpdc.1995.1010

Embedding K-ary Complete Trees into Hypercubes

X. J. Shen
, Q. Hu
, W. F. Liang

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

15 Citations (Scopus)

Abstract

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=0Cⁱ_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. © 1995 Academic Press. All rights reserved.

Original language	English
Pages (from-to)	100-106
Journal	Journal of Parallel and Distributed Computing
Volume	24
Issue number	1
DOIs	https://doi.org/10.1006/jpdc.1995.1010
Publication status	Published - Jan 1995
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Access Output

10.1006/jpdc.1995.1010

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{9a65277082894620a424f58d0f8a6622,

title = "Embedding K-ary Complete Trees into Hypercubes",

abstract = "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, TK(h), into an (h - 1)[log K] + [log (K + 2)]-dimensional hypercube with dilation Max\{2, φ(K), φ(K + 2)\}. φ(x) = min\{λ: Σλi=0Cid ≥ 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 TK(h) as its subgraph, K ≥ 3. {\textcopyright} 1995 Academic Press. All rights reserved.",

author = "Shen, \{X. J.\} and Q. Hu and Liang, \{W. F.\}",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1995",

month = jan,

doi = "10.1006/jpdc.1995.1010",

language = "English",

volume = "24",

pages = "100--106",

journal = "Journal of Parallel and Distributed Computing",

issn = "0743-7315",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Embedding K-ary Complete Trees into Hypercubes

AU - Shen, X. J.

AU - Hu, Q.

AU - Liang, W. F.

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1995/1

Y1 - 1995/1

N2 - 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, TK(h), into an (h - 1)[log K] + [log (K + 2)]-dimensional hypercube with dilation Max{2, φ(K), φ(K + 2)}. φ(x) = min{λ: Σλi=0Cid ≥ 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 TK(h) as its subgraph, K ≥ 3. © 1995 Academic Press. All rights reserved.

AB - 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, TK(h), into an (h - 1)[log K] + [log (K + 2)]-dimensional hypercube with dilation Max{2, φ(K), φ(K + 2)}. φ(x) = min{λ: Σλi=0Cid ≥ 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 TK(h) as its subgraph, K ≥ 3. © 1995 Academic Press. All rights reserved.

UR - https://www.scopus.com/pages/publications/0038956352

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0038956352&origin=recordpage

U2 - 10.1006/jpdc.1995.1010

DO - 10.1006/jpdc.1995.1010

M3 - RGC 21 - Publication in refereed journal

SN - 0743-7315

VL - 24

SP - 100

EP - 106

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 1

ER -

Embedding K-ary Complete Trees into Hypercubes

Abstract

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this