User: Guest  Login
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