The Library
Dense edge-disjoint embedding of binary trees in the mesh
Tools
Tools
Tools
Gibbons, Alan (Alan M.) and Paterson, Michael S. (1992) Dense edge-disjoint embedding of binary trees in the mesh. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-208.pdf - Other - Requires a PDF viewer. Download (4Mb) | Preview |
Abstract
We present an embedding of the complete binary tree with n leaves in the Vn x Vn mesh, for any n = 2exp(2m) where m is a positive integer. The embedding has the following properties: at most two tree nodes (one of which is a leaf) are mapped onto each mesh node, paths of the tree are mapped onto edge-disjoint paths in the mesh (each mesh edge considered as two anti-parallel directed edges) and the maximum distance from a leaf to the root of the tree is Vn + O (log n) mesh steps. This embedding facilitates efficient implementation of many P-RAM algorithms on the mesh, particularly those using the balanced binary tree technique. Such an embedding offers greater flexibility of use and improves the time complexity of these implementations by a constant factor compared with previously described embeddings.
| 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), Parallel processing (Electronic computers) | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | February 1992 | ||||
| Dates: |
|
||||
| Number: | Number 208 | ||||
| Number of Pages: | 9 | ||||
| DOI: | CS-RR-208 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | A.M. Gibbons and M. Paterson, “Dense Edge-Disjoint Embedding of Binary Trees in the Mesh”, <i>Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '92)</i>, San Diego, CA, ACM Press, New York, NY, pp. 257-263 (1992) | ||||
| Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | 3075 (ESPRIT) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
