The Library
Dense edge-disjoint embedding of complete binary trees in interconnection networks
Tools
Tools
Tools
Ravindran, Somasundaram, Gibbons, Alan (Alan M.) and Paterson, Michael S. (1995) Dense edge-disjoint embedding of complete binary trees in interconnection networks. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-284.pdf - Other - Requires a PDF viewer. Download (335Kb) | Preview |
Abstract
We describe dense edge-disjoint embeddings of the complete binary tree with n leaves in the following n-node communication networks: the hypercube, the de Bruijn and shuffle-exchange networks and the two-dimensional mesh. For the mesh and the shuffle-exchange graphs each edge is regarded as two parallel (or anti-parallel) edges. The embeddings have the following properties: paths of the tree are mapped onto edge-disjoint paths of the host graph and at most two tree nodes (just one of which is a leaf) are mapped onto each host node. We prove that the maximum distance from a leaf to the root of the tree is asymptotically as short as possible in all host graphs except in the case of the shuffle-exchange, in which case we conjecture that it is as short as possible. The embeddings facilitate efficient implementation of many P-RAM algorithms on these networks.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Trees (Graph theory), Communication -- Network analysis, Parallel processing (Electronic computers) | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | 1995 | ||||
| Dates: |
|
||||
| Number: | Number 284 | ||||
| Number of Pages: | 18 | ||||
| DOI: | CS-RR-284 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Funder: | Science and Engineering Research Council (Great Britain) (SERC), European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | GR/H/76487 (SERC), 7141 (ESPRIT) | ||||
| Version or Related Resource: | Ravindrana, S., Gibbons, A.M. and Paterson, M.S. (2000). Dense edge-disjoint embedding of complete binary trees in interconnection networks. Theoretical Computer Science, 249(2). | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
