- INSTANCE:
Graph
, and a collection
of subsets
called required sets, where
is the set of
.
- SOLUTION: A set of unordered node pairs such that each is contained in a connected component of .
- COST FUNCTION: .
- OBJECTIVE:
Minimize.
*Approx.:*Approximable within [12].*Hardness:*APX- hard.[87],[13]*Comment:*defines a -Metric on where is the set of node pairs which are at distance one from each other, and all other node pairs are at distance

2015-04-27 Revision: 288 PDF version