# The ICICS/CS Reading Room

## UBC CS TR-90-28 Summary

- No on-line copy of this technical report is available.

- Parallel Techniques for Construction of Trees and Related Problems, October 1990 Teresa Maria Przytycka
The concept of a tree has been used in various areas of mathematics for over a
century. In particular, trees appear to be one of the most fundamental notions in computer
science. Sequential algorithms for trees are generally well studied. Unfortunately many of
these sequential algorithms use methods which seem to be inherently sequential. One of the
contributions of this thesis is the introduction of several parallel-techniques for the
construction of various types of trees and the presentation of new parallel tree construction
algorithms using these methods. Along with the parallel tree construction techniques
presented here, we develop techniques which have broader applications.
\n We use the Parallel Random Access Machine as our model of computation. We
consider two basic methods of constructing trees: {\em tree expansion} and {\em tree synthesis}.
\n In the {\em tree expansion method}, we start with a single vertex and construct a tree by
adding nodes of degree one and/or by subdividing edges. We use the parallel tree
expansion technique to construct the tree representation for graphs in the family of graphs
known as cographs.
\n In the {\em tree synthesis method}, we start with a forest of single node subtrees and
construct a tree by adding edges or (for rooted trees) by creating parent nodes for some
roots of the trees in the forest. We present a family of parallel and sequential algorithms to
construct various approximations to the Huffman tree. All these algorithms apply the tree
synthesis method by constructing a tree in a level-by-level fashion. To support one of the
algorithms in the family we develop a technique which we call the {\em cascading sampling
technique}.
\n One might suspect that the parallel tree synthesis method can be applied only to trees
of polylogarithmic height, but this is not the case.We present a technique which we call the
{\em valley filling technique} and develop its accelerated version called the {\em accelerated valley
filling technique}. We present an application of this technique to an optimal parallel
algorithm for construction of minimax trees.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.