From: utzoo!watmath!mwang
Newsgroups: ont.events
Title: UW Theory Seminar, Prof. Ruzzo will give a talk
Article-I.D.: watmath.4182
Posted: Wed Jan  5 13:02:47 1983
Received: Thu Jan  6 00:04:21 1983
Expires: Sat Jan  8 00:00:00 1983


               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