<%@ 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-223

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

Somasundaram Ravindran and A.M. Gibbons, Dense Edge-Disjoint Embedding of Complete Binary Trees in the Hypercube (July 1, 1992).

Abstract

We show that the complete binary tree with n > 8 leaves can be embedded in the hypercube with n nodes such that: paths of the tree are mapped onto edge-disjoint paths of the hypercube, at most two tree nodes (one of which is a leaf) are mapped onto each hypercube node, and the maximum distance from a leaf to the root of the tree is log_2 n + 1 hypercube edges (which is optimally short). This embedding facilitates efficient implementation of many P-RAM algorithms on the hypercube. keywords: parallel algorithms, graph embedding, binary tree, hypercube

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

S. Ravindran and A.M. Gibbons, "Dense Edge-Disjoint Embedding of Complete Binary Trees in the Hypercube", Information Processing Letters 45(6), pp. 321-325 (1993)

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