Login
- Dokumenttyp:
- Report / Forschungsbericht
- Autor(en):
- Matthias Baumgart; Hanjo Täubig
- Titel:
- 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.
- Stichworte:
- Spanning tree; distance approximation; minimum fundamental cycle basis; network abstraction
- Jahr:
- 2008
- Seiten/Umfang:
- 10
- Sprache:
- de
- Format:
- Text
BibTeX