Document type:
Technical Report
Author(s):
Stefan Eckhhardt; Sebastian Wernicke
Title:
On the Algorithmic Intractability of Computing Distance-Approximating Spanning Trees
Abstract:
This work presents novel results concerning the algorithmic intractability and inapproximability of computing \textsc{Minimum Distance-Approximating Spanning Trees (DAST)} with respect to a range of common matrix norms. Formally, we analyze the problem of computing a spanning tree $T$ for a given graph $G$ such that the difference $(D_T-D_G)$ of the respective distance matrices is minimal with respect to the matrix norms \emph{maximum-entry}, \emph{Minkowski-distance}, \emph{maximum column-sum},...    »

Keywords:
spanning tree; additive spanner; distance-approximating; minimum spanning tree; inapproximability; computational complexity; NP-complete
Year:
2004
Year / month:
2004-07-01 00:00:00
Pages:
34