Benutzer: Gast  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