<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-208

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

A.M. Gibbons and M.S. Paterson, Dense Edge-Disjoint Embedding of Binary Trees in the Mesh (February 1, 1992).

Abstract

We present an embedding of the complete binary tree with n leaves in the Vn x Vn mesh, for any n = 2exp(2m) 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 considered as two anti-parallel directed edges) and the maximum distance from a leaf to the root of the tree is Vn + O (log n) mesh steps. This embedding facilitates efficient implementation 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 implementations by a constant factor compared with previously described embeddings.

<%@ include file="cited.html" %>

A.M. Gibbons and M. Paterson, "Dense Edge-Disjoint Embedding of Binary Trees in the Mesh", Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '92), San Diego, CA, ACM Press, New York, NY, pp. 257-263 (1992)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>