Tutte seminar - Joseph Cheriyan

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


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.