Next: Stochastic Steiner Tree Problem
Up: Steiner Tree Problems
Previous: Zero Skew Tree Problem
, 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 14 when the root is not fixed as a part of the instance .
when the root is given as part of the input .
NP-hard . Also NP-hard in the two-dimensional rectilinear case .
2015-04-27 Revision: 288 PDF version