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. (2000) Dense edge-disjoint embedding of complete binary trees in interconnection networks. Theoretical Computer Science, Volume 249 (Number 2). pp. 325-342.
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1016/S0304-3975(00)00066-9
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: | Journal Item | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Journal or Publication Title: | Theoretical Computer Science | ||||
| Publisher: | Elsevier Science BV | ||||
| ISSN: | 0304-3975 | ||||
| Official Date: | 28 October 2000 | ||||
| Dates: |
|
||||
| Volume: | Volume 249 | ||||
| Number: | Number 2 | ||||
| Number of Pages: | 18 | ||||
| Page Range: | pp. 325-342 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Version or Related Resource: | Ravindrana, S., Gibbons, A.M. and Paterson, M.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, 284). | ||||
| Title of Event: | 9th Australasian Workshop on Combinatorial Algorithms (AWOCA 98) | ||||
| Location of Event: | Perth, Australia | ||||
| Date(s) of Event: | 27-30 Jul 1998 | ||||
| Related URLs: |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
