Tutte seminar - Joseph Cheriyan

Packing Element-Disjoint Steiner Trees

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.