Dense edge-disjoint embedding of complete binary trees in interconnection networks (Q1583538)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dense edge-disjoint embedding of complete binary trees in interconnection networks |
scientific article |
Statements
Dense edge-disjoint embedding of complete binary trees in interconnection networks (English)
0 references
26 October 2000
0 references
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.
0 references
parallel algorithms
0 references
graph embedding
0 references
binary tree
0 references
hypercube
0 references
mesh
0 references
De Bruijn network
0 references
shuffle-exchange network
0 references
0 references