Next: Bounded Skew Tree Problem
Up: Steiner Tree Problems
Previous: Quality of Service Multicast
, set of sinks
, edge costs
A stretched tree
consisting of an arborescence
is a one-to-one mapping between the leaves of
and a cost function
for every edge
and furthermore, for each pair
of root-to-leaf paths in
- COST FUNCTION:
Approximable within approximation ratio 4 when the root is not fixed as a part of the instance .
Approximable within approximation ratio
if the root is fixed .
The complexity of the rectilinear zero skew tree problem is not known. For a fixed tree topology, the problem can be solved in linear time by using the Deferred-Merge Embedding (DME) , , .
2015-04-27 Revision: 288 PDF version