|
Friday, November 21, 2008 |
|
|
|
|
Packing Element-Disjoint Steiner Trees |
|
|
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. |