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