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

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this