Dense edge-disjoint embedding of complete binary trees in interconnection networks
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.
- Dense edge-disjoint embedding of complete binary trees in the hypercube
- On the fault-tolerant embeddings of complete binary trees in the mesh interconnection networks
- scientific article; zbMATH DE number 1103048
- Incomplete hypercubes: Embeddings of tree-related networks
- Embedding complete binary trees into star networks
- A class of problems efficiently solvable on mesh-connected computers including dynamic expression evaluation
- An optimal routing algorithm for mesh-connected Parallel computers
- Dense edge-disjoint embedding of complete binary trees in the hypercube
- scientific article; zbMATH DE number 3858396 (Why is no real title available?)
- scientific article; zbMATH DE number 43583 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- The balanced binary tree technique on mesh-connected computers
- Embedding complete k-ary trees into k-square 2-D meshes with optimal edge congestion
- On the fault-tolerant embeddings of complete binary trees in the mesh interconnection networks
- Dense edge-disjoint embedding of complete binary trees in the hypercube
- Wheel-augmented binary trees
- scientific article; zbMATH DE number 1103048 (Why is no real title available?)
- scientific article; zbMATH DE number 6297807 (Why is no real title available?)
- Algorithms and Computation
- Tree embeddings for hop-constrained network design
- Embedding complete binary trees in product graphs
This page was built for publication: Dense edge-disjoint embedding of complete binary trees in interconnection networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583538)
