# Sebastian Wernicke: Distanzapproximierende Spannbäume

Attributes such as structural simplicity and sparseness make spanning trees
an attractive tool for representing a network througha small number of edges
whilst maintainingconnectivity. Several optimization problems have been
considered that try to find a spanning tree which approximates certain
properties of the underlying network (e.g., the diameter or the sum of all
distances). In this work, we consider the optimality criterion of
distance-approximation, i.e., vertices that have a small distance to each
other in the original graph should maintain this property in the spanning
tree. Integrating the problems into a unifying framework based on matrix
norms, we show that all of the optimization problems related to
distance-approximationare not only NP hard---unless P=NP some of them even
do not allow for a constant-factor approximation in polynomial time.