Login
- Document type:
- Report / Forschungsbericht
- Author(s):
- Matthias Baumgart; Hanjo Täubig
- Title:
- The Complexity of Computing Graph-Approximating Spanning Trees
- Abstract:
- This paper deals with the problem of computing a spanning tree of a connected undirected graph G=(V,E) minimizing the sum of distance differences of all vertex pairs u,v\in V which are connected by an edge {u,v}\in E. We show that the decision variant of this optimization problem is NP-complete with respect to the L_p norm for arbitrary p\in N. For the reduction, we use the well known NP-complete problem Vertex Cover.
- Keywords:
- Spanning tree; distance approximation; minimum fundamental cycle basis; network abstraction
- Year:
- 2008
- Pages:
- 10
- Language:
- de
- Format:
- Text
BibTeX