  We study the problem of finding small trees. Classical network design
problems are considered with the additional constraint that only a specified
number $k$ of nodes are required to be connected in the solution. A
prototypical example is the $k$MST problem in which we require a tree of
minimum weight spanning at least $k$ nodes in an edge-weighted graph. We show
that the $k$MST problem is NP-hard even for points in the Euclidean plane. We
provide approximation algorithms with performance ratio $2\sqrt{k}$ for the
general edge-weighted case and $O(k^{1/4})$ for the case of points in the
plane. Polynomial-time exact solutions are also presented for the class of
decomposable graphs which includes trees, series-parallel graphs, and bounded
bandwidth graphs, and for points on the boundary of a convex region in the
Euclidean plane. We also investigate the problem of finding short trees, and
more generally, that of finding networks with minimum diameter. A simple
technique is used to provide a polynomial-time solution for finding $k$-trees
of minimum diameter. We identify easy and hard problems arising in finding
short networks using a framework due to T. C. Hu.
