Dense edge-disjoint embedding of complete binary trees in interconnection networks
UNSPECIFIED (2000) Dense edge-disjoint embedding of complete binary trees in interconnection networks. In: 9th Australasian Workshop on Combinatorial Algorithms (AWOCA 98), SCH COMP CURTIN UNIV TECHNOL, PERTH, AUSTRALIA, JUL 27-30, 1998. Published in: THEORETICAL COMPUTER SCIENCE, 249 (2). pp. 325-342.Full text not available from this repository.
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. (C) 2000 Elsevier Science B.V. All rights reserved.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Journal or Publication Title:||THEORETICAL COMPUTER SCIENCE|
|Publisher:||ELSEVIER SCIENCE BV|
|Date:||28 October 2000|
|Number of Pages:||18|
|Page Range:||pp. 325-342|
|Title of Event:||9th Australasian Workshop on Combinatorial Algorithms (AWOCA 98)|
|Location of Event:||SCH COMP CURTIN UNIV TECHNOL, PERTH, AUSTRALIA|
|Date(s) of Event:||JUL 27-30, 1998|
Actions (login required)