Degree-Preserving Forests

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)

Update: 1998-12-10

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