by **
H. Broersma, A. Huck, T. Kloks, O. Koppius, D. Kratsch, H. Müller, H.: Tuinstra**

**Preprint series:**
98-08, Reports on Computer Science and Algebra and Geometry

**The paper is published:**
Springer-Verlag
Lecture Notes in Computer Science 1517 (1998) 88-99.

**MSC:**- 05C05 Trees

**Abstract:** 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 e.g., 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. We present linear time approximation algorithms for planar graphs of worst case performance ratio $1-\epsilon$ for every constant $\epsilon$ > 0. Furthermore we give exact algorithms for interval graphs (linear time), graphs of bounded treewidth (linear time), cocomparability graphs (O(n^4)), and graphs of bounded asteroidal number.

**Keywords:** *degree-preserving spanning tree (DPST)*

**Upload:** 1998-12-10

**Update:** 1998-12-10

The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.