Optimal embedding of incomplete binary trees onto incomplete hypercubes

Chien Hung Huang, Ju-Yuan Hsiao, R. C.T. Lee, Jywe Fei Fang

Research output: Contribution to journalConference article

1 Citation (Scopus)

Abstract

It has been proved that incomplete binary trees can not be embedded onto incomplete hypercubes with both expansion-1 and dilation-1. In this paper, we propose an optimal embedding algorithm to embed this issue with expansion-1, dilation-2. Our algorithm is a linear time algorithm, which is optimal in terms of time complexity. Furthermore, the embedding scheme is as desirable to be simple such that the implementation is quite easy.

Original languageEnglish
Pages (from-to)80-85
Number of pages6
JournalProceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
Publication statusPublished - 1999 Dec 1
EventProceedings of the 1999 4th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'99) - Perth/Fremantle, Aust
Duration: 1999 Jun 231999 Jun 25

Fingerprint

Binary trees

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

@article{2812e81505754c9e97f5dd28c1420ef0,
title = "Optimal embedding of incomplete binary trees onto incomplete hypercubes",
abstract = "It has been proved that incomplete binary trees can not be embedded onto incomplete hypercubes with both expansion-1 and dilation-1. In this paper, we propose an optimal embedding algorithm to embed this issue with expansion-1, dilation-2. Our algorithm is a linear time algorithm, which is optimal in terms of time complexity. Furthermore, the embedding scheme is as desirable to be simple such that the implementation is quite easy.",
author = "Huang, {Chien Hung} and Ju-Yuan Hsiao and Lee, {R. C.T.} and Fang, {Jywe Fei}",
year = "1999",
month = "12",
day = "1",
language = "English",
pages = "80--85",
journal = "Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN",
issn = "1087-4089",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

Optimal embedding of incomplete binary trees onto incomplete hypercubes. / Huang, Chien Hung; Hsiao, Ju-Yuan; Lee, R. C.T.; Fang, Jywe Fei.

In: Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, 01.12.1999, p. 80-85.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Optimal embedding of incomplete binary trees onto incomplete hypercubes

AU - Huang, Chien Hung

AU - Hsiao, Ju-Yuan

AU - Lee, R. C.T.

AU - Fang, Jywe Fei

PY - 1999/12/1

Y1 - 1999/12/1

N2 - It has been proved that incomplete binary trees can not be embedded onto incomplete hypercubes with both expansion-1 and dilation-1. In this paper, we propose an optimal embedding algorithm to embed this issue with expansion-1, dilation-2. Our algorithm is a linear time algorithm, which is optimal in terms of time complexity. Furthermore, the embedding scheme is as desirable to be simple such that the implementation is quite easy.

AB - It has been proved that incomplete binary trees can not be embedded onto incomplete hypercubes with both expansion-1 and dilation-1. In this paper, we propose an optimal embedding algorithm to embed this issue with expansion-1, dilation-2. Our algorithm is a linear time algorithm, which is optimal in terms of time complexity. Furthermore, the embedding scheme is as desirable to be simple such that the implementation is quite easy.

UR - http://www.scopus.com/inward/record.url?scp=0033360350&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033360350&partnerID=8YFLogxK

M3 - Conference article

SP - 80

EP - 85

JO - Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN

JF - Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN

SN - 1087-4089

ER -