
The Library
Dense edge-disjoint embedding of complete binary trees in the hypercube
Tools
Ravindran, Somasundaram and Gibbons, Alan (Alan M.) (1992) Dense edge-disjoint embedding of complete binary trees in the hypercube. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-223.pdf - Other - Requires a PDF viewer. Download (3193Kb) | Preview |
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 log2 n + 1 hypercube edges (which is optimally short). This embedding facilitates efficient implementation of many P-RAM algorithms on the hypercube.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Trees (Graph theory), Hypercube, Parallel algorithms | ||||
Series Name: | Department of Computer Science research report | ||||
Publisher: | University of Warwick. Department of Computer Science | ||||
Official Date: | February 1992 | ||||
Dates: |
|
||||
Number: | Number 223 | ||||
Number of Pages: | 6 | ||||
DOI: | CS-RR-223 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Reuse Statement (publisher, data, author rights): | S. Ravindran and A.M. Gibbons, “Dense Edge-Disjoint Embedding of Complete Binary Trees in the Hypercube”, <i>Information Processing Letters</i> <b>45</b>(6), pp. 321-325 (1993) | ||||
Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
Grant number: | 7141 (ESPRIT) | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |