Speaker: Mohammad R. Salavatipour, University of Toronto
Time:    Thursday, January 23, 2:00 p.m.
Place:   room: HP4351, School of Math and Stats, Carleton University
Title:   Packing Steiner Trees

Abstract:
The Steiner packing problem is to find the maximum number of edge-disjoint
subgraphs of a given graph $G$ that connect a given set of required points
$S$. This problem is motivated by practical applications in VLSI-layout
and broadcasting, as well as theoretical reasons. In this paper, we study
this problem and present an algorithm with an asymptotic approximation
factor of $|S|/4$. This gives a sufficient condition for the existence of
$k$ edge-disjoint Steiner trees in a graph in terms of the
edge-connectivity of the graph. We will show that this condition is
the best possible if the number of terminals is 3. At the end, we consider
the fractional version of this problem, and observe that it can be reduced
to the minimum Steiner tree problem via the ellipsoid algorithm.
This paper is to appear in SODA 2003 and it is a joint work with:
   Kamal Jain (Microsoft Research)
   Mohammad Mahdian (CS Lab, MIT)