- INSTANCE:
Finite set of
terminal pairs
.
- SOLUTION:
A forest
such that for all
, vertices
and
are contained in the same connected component of
.
- COST FUNCTION:
The Euclidean length
of
, where
denotes the Euclidean Norm in
.
- OBJECTIVE:
Minimize
*Approx.:*Admits a PTAS [20].*Hardness:*NP-hard [7].*Comment:*-dimensional version where admits a PTAS for being constant. For the problem is APX-hard [102].

2015-04-27 Revision: 288 PDF version