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)

Preview

PDF (Department of Computer Science Research Report) WRAP_cs-rr-223.pdf - Other - Requires a PDF viewer. Download (3193Kb) | Preview

Request Changes to record.

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 > 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:	Date Event February 1992 Completion
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
Publisher Statement:	S.&nbsp;Ravindran and A.M.&nbsp;Gibbons, &ldquo;Dense Edge-Disjoint Embedding of Complete Binary Trees in the Hypercube&rdquo;, <i>Information Processing Letters</i> <b>45</b>(6), pp.&nbsp;321-325 (1993)
Funder:	European Strategic Programme of Research and Development in Information Technology (ESPRIT)
Grant number:	7141 (ESPRIT)
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads