Degree-preserving forests

Haitze J. Broersma, Andreas Huck, A.J.J. Kloks, 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 languageUndefined
Title of host publicationMathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98
Place of PublicationBerlin
PublisherSpringer
Pages713-721
Number of pages10
ISBN (Print)3-540-64827-5
DOIs
Publication statusPublished - 1998

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Number1450
Volume1450
ISSN (Print)0302-9743

Keywords

  • METIS-141078
  • IR-92413

Cite this

Broersma, H. J., Huck, A., Kloks, A. J. J., Kloks, T., Koppius, O., Kratsch, D., ... Tuinstra, H. (1998). Degree-preserving forests. In Mathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98 (pp. 713-721). (Lecture Notes in Computer Science; Vol. 1450, No. 1450). Berlin: Springer. https://doi.org/10.1007/BFb0055822
Broersma, Haitze J. ; Huck, Andreas ; Kloks, A.J.J. ; Kloks, Ton ; Koppius, Otto ; Kratsch, Dieter ; Müller, Haiko ; Tuinstra, Hilde. / Degree-preserving forests. Mathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98. Berlin : Springer, 1998. pp. 713-721 (Lecture Notes in Computer Science; 1450).
@inbook{f98214b3b17d498bbd8af78ed3d7e314,
title = "Degree-preserving forests",
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.",
keywords = "METIS-141078, IR-92413",
author = "Broersma, {Haitze J.} and Andreas Huck and A.J.J. Kloks and Ton Kloks and Otto Koppius and Dieter Kratsch and Haiko M{\"u}ller and Hilde Tuinstra",
year = "1998",
doi = "10.1007/BFb0055822",
language = "Undefined",
isbn = "3-540-64827-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "1450",
pages = "713--721",
booktitle = "Mathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98",

}

Broersma, HJ, Huck, A, Kloks, AJJ, Kloks, T, Koppius, O, Kratsch, D, Müller, H & Tuinstra, H 1998, Degree-preserving forests. in Mathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98. Lecture Notes in Computer Science, no. 1450, vol. 1450, Springer, Berlin, pp. 713-721. https://doi.org/10.1007/BFb0055822

Degree-preserving forests. / Broersma, Haitze J.; Huck, Andreas; Kloks, A.J.J.; Kloks, Ton; Koppius, Otto; Kratsch, Dieter; Müller, Haiko; Tuinstra, Hilde.

Mathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98. Berlin : Springer, 1998. p. 713-721 (Lecture Notes in Computer Science; Vol. 1450, No. 1450).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

TY - CHAP

T1 - Degree-preserving forests

AU - Broersma, Haitze J.

AU - Huck, Andreas

AU - Kloks, A.J.J.

AU - Kloks, Ton

AU - Koppius, Otto

AU - Kratsch, Dieter

AU - Müller, Haiko

AU - Tuinstra, Hilde

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - METIS-141078

KW - IR-92413

U2 - 10.1007/BFb0055822

DO - 10.1007/BFb0055822

M3 - Chapter

SN - 3-540-64827-5

T3 - Lecture Notes in Computer Science

SP - 713

EP - 721

BT - Mathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98

PB - Springer

CY - Berlin

ER -

Broersma HJ, Huck A, Kloks AJJ, Kloks T, Koppius O, Kratsch D et al. Degree-preserving forests. In Mathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98. Berlin: Springer. 1998. p. 713-721. (Lecture Notes in Computer Science; 1450). https://doi.org/10.1007/BFb0055822