Friday, November 21, 2008 3:30 pm
-
4:30 pm
EST (GMT -05:00)
Packing Element-Disjoint Steiner Trees
Speaker: | Joseph Cheriyan |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
We present some hardness results and approximation algorithms for the problem of packing element-disjoint Steiner trees in graphs. Given a graph with a designated subset of terminal nodes, the goal is to find a maximum-cardinality set of trees such that each tree contains every terminal node, and each non-terminal node and each edge is in at most one tree.
Joint work with A. Aazami, K. R. Jampani, and M. R. Salavatipour.