DENSE EDGE-DISJOINT EMBEDDING OF COMPLETE BINARY-TREES IN THE HYPERCUBE
UNSPECIFIED (1993) DENSE EDGE-DISJOINT EMBEDDING OF COMPLETE BINARY-TREES IN THE HYPERCUBE. INFORMATION PROCESSING LETTERS, 45 (6). pp. 321-325. ISSN 0020-0190Full text not available from this repository.
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|
|Date:||16 April 1993|
|Number of Pages:||5|
|Page Range:||pp. 321-325|
Actions (login required)