Degree-preserving trees

Haitze J. Broersma, A.J.J. Kloks, Otto Koppius, Hilde Tuinstra, Andreas Huck, Ton Kloks, Dieter Kratsch, Haiko Müller

Research output: Contribution to journalArticleAcademicpeer-review

14 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)26-39
Number of pages14
JournalNetworks
Volume35
Issue number1
DOIs
Publication statusPublished - 2000

Keywords

  • Spanning tree
  • METIS-140629
  • interval graphs
  • planar graphs
  • asteroidal number
  • AT-free graphs
  • Complexity
  • Approximation
  • Algorithms
  • Graphs
  • Degree condition
  • NP-completeness
  • Treewidth
  • IR-71629
  • cocomparability graphs

Fingerprint Dive into the research topics of 'Degree-preserving trees'. Together they form a unique fingerprint.

Cite this