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.

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. (C) 2000 Elsevier Science B.V. All rights reserved.

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item