Degree-preserving trees

Broersma, Hajo and Koppius, Otto and Tuinstra, Hilde and Huck, Andreas and Kloks, Ton and Kratsch, Dieter and Müller, Haiko (2000) Degree-preserving trees. Networks, 35 (1). pp. 26-39. ISSN 0028-3045

PDF
Restricted to UT campus only: Request a copy
175Kb

Abstract:	We consider the degree-preserving spanning tree (DPST) problem: Given a connected graph G, find a spanning tree T of G such that as many vertices of T as possible have the same degree in T as in G. This problem is a graph-theoretical translation of a problem arising in the system-theoretical context of identifiability in networks, a concept which has applications in, for example, water distribution networks and electrical networks. We show that the DPST problem is NP-complete, even when restricted to split graphs or bipartite planar graphs, but that it can be solved in polynomial time for graphs with a bounded asteroidal number and for graphs with a bounded treewidth. For the class of interval graphs, we give a linear time algorithm. For the class of cocomparability graphs, we give an O(n4) algorithm. Furthermore, we present linear time approximation algorithms for planar graphs of a worst-case performance ratio of 1 - ε for every ε > 0.
Item Type:	Article
Copyright:	© 2000 Wiley InterScience
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/71629
Official URL:	http://dx.doi.org/10.1002/(SICI)1097-0037(200001)35:1<26::AID-NET3>3.0.CO;2-M
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page

Metis ID: 140629