Optimal embedding of incomplete binary trees onto incomplete hypercubes

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

Optimal embedding of incomplete binary trees onto incomplete hypercubes

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

資訊工程學系

研究成果: Conference article › 同行評審

1 引文斯高帕斯（Scopus）

摘要

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.

原文	English
頁（從 - 到）	80-85
頁數	6
期刊	Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
出版狀態	Published - 1999 十二月 1
事件	Proceedings of the 1999 4th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'99) - Perth/Fremantle, Aust 持續時間: 1999 六月 23 → 1999 六月 25

All Science Journal Classification (ASJC) codes

Computer Science(all)

存取文件

指紋深入研究「Optimal embedding of incomplete binary trees onto incomplete hypercubes」主題。共同形成了獨特的指紋。

引用此

@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 = dec,

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.",

note = "Proceedings of the 1999 4th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'99) ; Conference date: 23-06-1999 Through 25-06-1999",

}

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

AN - SCOPUS:0033360350

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

T2 - Proceedings of the 1999 4th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'99)

Y2 - 23 June 1999 through 25 June 1999

ER -