The Library
DENSE EDGE-DISJOINT EMBEDDING OF COMPLETE BINARY-TREES IN THE HYPERCUBE
Tools
UNSPECIFIED (1993) DENSE EDGE-DISJOINT EMBEDDING OF COMPLETE BINARY-TREES IN THE HYPERCUBE. INFORMATION PROCESSING LETTERS, 45 (6). pp. 321-325. ISSN 0020-0190.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
We show that the complete binary tree with n > 8 leaves can be embedded in the hypercube with n nodes such that: paths of the tree are mapped onto edge-disjoint paths of the hypercube, at most two tree nodes (one of which is a leaf) are mapped onto each hypercube node, and the maximum distance from a leaf to the root of the tree is log2n + 1 hypercube edges (which is optimally short). This embedding facilitates efficient implementation of many P-RAM algorithms on the hypercube.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Journal or Publication Title: | INFORMATION PROCESSING LETTERS | ||||
Publisher: | ELSEVIER SCIENCE BV | ||||
ISSN: | 0020-0190 | ||||
Official Date: | 16 April 1993 | ||||
Dates: |
|
||||
Volume: | 45 | ||||
Number: | 6 | ||||
Number of Pages: | 5 | ||||
Page Range: | pp. 321-325 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |