Degree-preserving forests

Hajo Broersma, Andreas Huck, Ton Kloks, Otto Koppius, Dieter Kratsch, Haiko Müller, Hilde Tuinstra

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

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−ε for every constant ε > 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.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 1998
Subtitle of host publication23rd International Symposium, MFCS'98 Brno, Czech Republic, August 24–28, 1998, Proceedings
EditorsLuboš Brim, Jozef Gruska, Jiří Zlatuška
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages713-721
Number of pages10
ISBN (Electronic)978-3-540-68532-6
ISBN (Print)978-3-540-64827-7
DOIs
Publication statusPublished - 1998
Event23rd International Symposium on Mathematical Foundations of Computer Science, MFCS 1998 - Brno, Czech Republic
Duration: 24 Aug 199828 Aug 1998
Conference number: 23

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume1450
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd International Symposium on Mathematical Foundations of Computer Science, MFCS 1998
Abbreviated titleMFCS
CountryCzech Republic
CityBrno
Period24/08/9828/08/98

Keywords

  • Span tree
  • Planar graph
  • Interval graph
  • Chordal graph
  • Linear time algorithm

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

Cite this