### Technical Report No. 30, July 1991 - Abstract

**Edmund Ihler, Gabriele Reich, Peter Widmayer:**

*On Shortest Networks for Classes of Points in the Plane*

We are given a set *P* of points in the plane, together with a
partition of *P* into *classes* of points;
i.e., each point of *P* belongs to exactly one class.
For a given network optimization problem, such as finding a
minimum spanning tree or finding a minimum diameter spanning tree,
we study the problem of choosing a subset *P'* of *P* that contains
at least one point of each class and solving the network
optimization problem for *P'*, such that the solution is optimal
among all possible choices for *P'*.
We show that solving the minimum spanning tree problem for classes
of points is defined by any of the Minkowski metrics *L_p*,
*1 <= p <= infinity*.
In contrast, a class solution for the minimum diameter spanning
tree problem can be computed in time *O(|P|^3)*.

By proving the NP-completeness of the minimum spanning tree class problem we also get some results for distance graphs. Here, computing a class solutioin for the minimum spanning tree problem is NP-complete, even under several restrictions, e.g., if the graph is part of a unit grid and is a tree, where the vertex degree and the numver of vertices per class are both bounded by three. This is true even if the graph is a minimum spanning tree for its set of vertices

report30.ps.gz