Back to search

University of British Columbia

Algorithms for embedding binary trees into hypercubes

Abstract

dc:description

The problem of embedding a guest graph G into a host graph H arises in the process of mapping a parallel program to a multicomputer. The communication structure of the program is represented by G, the interconnection network of the multicomputer is represented by H and the goal is to embed G into H such that some measure of the communication cost is minimized. In general, this problem is N P-complete and several types of approximation algorithms have been proposed. We evaluate these algorithms empirically using hypercube host graphs and binary tree guest graphs. These families of graphs are interesting because of the existence of both heuristic techniques and theoretical algorithms for this problem. Although for general trees the problem is N P-complete, for binary trees the complexity remains open. We have implemented and experimented with several different algorithms and discovered variations of a greedy approach which produce close to optimal solutions in a reasonable amount of time.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1989

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Smedley, Garth Peter

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/27635

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Smedley, Garth Peter. Algorithms for embedding binary trees into hypercubes. master's thesis, University of British Columbia, 1989. http://hdl.handle.net/2429/27635