DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

           Steiner Trees in the Plane: Algorithms and Applications           

                              Martin Zachariasen                             
                        Department of Computer Science                       
                           University of Copenhagen                          

                    Tuesday, December 8, 1998, at 2:15 PM                    
                               The Seminar Room                              


We consider the  following fundamental network  design problem,  denoted the
Steiner tree problem in the plane: Given a  set of points (terminals) in the
plane, construct a  tree interconnecting all  terminals such that  the total
length of all  line segments  is minimized.  In  the Euclidean  Steiner tree
problem, the  length of  a  line segment  is the  usual  Euclidean (or  L_2)
distance between  the endpoints  of  the segment.  Correspondingly,  in  the
rectilinear  Steiner  tree   problem  distances   are  measured   using  the
rectilinear (or L_1) distance metric.  In this talk, we will describe recent
exact and heuristic algorithms  for these two  problems.  The new algorithms
allow the  exact  solution  of  real-life  instances  with  more  than  2000
terminals. Applications of the rectilinear problem in VLSI design are given.
Also, we give a short introduction to  the important generalization in which
a set of polygonal obstacles  has to be avoided  by the tree interconnecting
the terminals.


                                                          Jørgen Bang-Jensen