- INSTANCE: Metric space , set of sinks , edge costs .
- SOLUTION: A stretched tree consisting of an arborescence , a mapping such that is a one-to-one mapping between the leaves of and and a cost function such that for every edge of , and furthermore, for each pair of root-to-leaf paths in , .
- COST FUNCTION:
- OBJECTIVE: Minimize.
*Approx.:*Approximable within approximation ratio 4 when the root is not fixed as a part of the instance [110]. Approximable within approximation ratio if the root is fixed [28].*Hardness:*NP-hard [28].*Comment:*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) [17], [26], [43].

2015-04-27 Revision: 288 PDF version