Can I read Dense Edge-disjoint Embedding of Binary Trees in the Mesh on EtoBox?

Dense Edge-disjoint Embedding of Binary Trees in the Mesh by Alan Gibbons; Michael Paterson is a scholarly article available to read on EtoBox.

What is Dense Edge-disjoint Embedding of Binary Trees in the Mesh about?

We present an embedding of the complete binary tree with n leaves in the & x & mesh, for any n = 22m where m is a positive integer. The embedding has the following properties: at most two tree nodes (one of which is a leaf) are mapped onto each mesh node, paths of the tree are mapped onto edge-disjoint paths in the mesh (each mesh edge being considered as two anti-parallel directed edges) and the maximum distance from a leaf to the root of the tree is fi + O (log n) mesh steps. This embedding facilitates efficient implement ation of many P-RAM algorithms on the mesh, particularly those using the balanced binary tree technique. Such an embedding offers greater flexibility of use and improves the time complexity of these implement ations by a constant factor compared with previously described embeddings.

Author

Alan Gibbons; Michael Paterson

Publisher

ACM

Published

1992

Language

EN