🚀 go-pugleaf

                           Dartmouth College
                      Computer Science Colloquium

                        Tuesday, Nov. 3, 1992
                        4:00 PM  102 Bradley
         Refreshments at 3:30pm in Faculty Lounge, 2nd floor

                         COMBINE AND CONQUER
 
                         Roberto Tamassia
                   Department of Computer Science
                         Brown University

The development of dynamic algorithms has acquired increasing
theoretical interest in the last years, and is motivated by many
important applications in computer graphics, database systems, network
optimization, and VLSI layout.  Dynamic (or incremental) computation
considers updating the solution of a problem when the problem instance
is modified.  Many applications are incremental (or
operation-by-operation) in nature.  Considerable savings can be
achieved if the new solution need not be generated ``from scratch,''
especially when the problem is large-scale.  A typical framework is to
process on-line a sequence of queries and updates on some structure
that evolves over time.  In this talk we present ``combine and
conquer'', a versatile technique that supports the dynamic evaluation
of computational graphs embedded into trees.  We also show
applications of this technique to graph and geometric problems.

(Joint work with R.F. Cohen.)

Note this colloquium is on TUESDAY rather than our usual WEDNESDAY.

For additional info please contact David Kotz at David.Kotz@dartmouth.edu.

Directions to Bradley Hall:
	   anonymous ftp to sunapee.dartmouth.edu in pub/directions
-- 
-----------------
Mathematics and Computer Science
Dartmouth College, 6188 Bradley Hall, Hanover NH 03755-3551
email: David.Kotz@Dartmouth.edu    or   dfk@cs.dartmouth.edu