mwang (01/05/83)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY SEMINAR - Friday, January 7, 1983.
Prof. W.L. Ruzzo of the University of Washington will
speak on "Embedding Trees in Balanced Trees, and Re-
lated Tricks".
TIME: 3:30 PM
ROOM: M&C 6091A
ABSTRACT
Hong, Mehlhorn, and Rosenberg have recently shown
that any binary tree can be embedded in a binary tree
of height O(log n) so that adjacent vertices in the
original tree are at most a constant distance apart
in the resulting balanced tree. This combinatorial
result has a number of interesting applications, in-
cluding new proofs of results by Brent on parallel
evaluation of arithmetic formulas and by myself
on parallel recognition of context-free languages.
It also seems to "summarize" a number of tree-
cutting lemmas used for various divide-and-conquer
algorithms on trees. In this talk I will survey
these developments, give a new, improved and
elementary proof of the embedding result, and a
new application of it to minimum edge-length planar
layouts of binary trees.
January 5, 1983