Degree-preserving forests

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

doi:10.1007/BFb0055822

Degree-preserving forests

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

7 Downloads (Pure)

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 language	English
Title of host publication	Mathematical Foundations of Computer Science 1998
Subtitle of host publication	23rd International Symposium, MFCS'98 Brno, Czech Republic, August 24–28, 1998, Proceedings
Editors	Luboš Brim, Jozef Gruska, Jiří Zlatuška
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	713-721
Number of pages	10
ISBN (Electronic)	978-3-540-68532-6
ISBN (Print)	978-3-540-64827-7
DOIs	https://doi.org/10.1007/BFb0055822
Publication status	Published - 1998
Event	23rd International Symposium on Mathematical Foundations of Computer Science, MFCS 1998 - Brno, Czech Republic Duration: 24 Aug 1998 → 28 Aug 1998 Conference number: 23

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	1450
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Symposium on Mathematical Foundations of Computer Science, MFCS 1998
Abbreviated title	MFCS
Country/Territory	Czech Republic
City	Brno
Period	24/08/98 → 28/08/98

Keywords

Span tree
Planar graph
Interval graph
Chordal graph
Linear time algorithm

Access to Document

10.1007/BFb0055822

Degree-preserving forests
Broersma, H. J., Huck, A., Kloks, A. J. J., Koppius, O., Kratsch, D., Müller, H. C. & Tuinstra, H., 1998, Prague: Charles University. 25 p. (KAM-DIMATIA Series; no. 98-402)
Research output: Book/Report › Report › Professional

Cite this

Broersma, H., Huck, A., Kloks, T., Koppius, O., Kratsch, D., Müller, H., & Tuinstra, H. (1998). Degree-preserving forests. In L. Brim, J. Gruska, & J. Zlatuška (Eds.), Mathematical Foundations of Computer Science 1998: 23rd International Symposium, MFCS'98 Brno, Czech Republic, August 24–28, 1998, Proceedings (pp. 713-721). (Lecture Notes in Computer Science; Vol. 1450). Springer. https://doi.org/10.1007/BFb0055822

@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 = "Span tree, Planar graph, Interval graph, Chordal graph, Linear time algorithm",

author = "Hajo Broersma and Andreas Huck and Ton Kloks and Otto Koppius and Dieter Kratsch and Haiko M{\"u}ller and Hilde Tuinstra",

year = "1998",

doi = "10.1007/BFb0055822",

language = "English",

isbn = "978-3-540-64827-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "713--721",

editor = "Lubo{\v s} Brim and Jozef Gruska and Ji{\v r}{\'i} Zlatu{\v s}ka",

booktitle = "Mathematical Foundations of Computer Science 1998",

address = "Germany",

note = "23rd International Symposium on Mathematical Foundations of Computer Science, MFCS 1998, MFCS ; Conference date: 24-08-1998 Through 28-08-1998",

}

Broersma, H, Huck, A, Kloks, T, Koppius, O, Kratsch, D, Müller, H & Tuinstra, H 1998, Degree-preserving forests. in L Brim, J Gruska & J Zlatuška (eds), Mathematical Foundations of Computer Science 1998: 23rd International Symposium, MFCS'98 Brno, Czech Republic, August 24–28, 1998, Proceedings. Lecture Notes in Computer Science, vol. 1450, Springer, Berlin, Heidelberg, pp. 713-721, 23rd International Symposium on Mathematical Foundations of Computer Science, MFCS 1998, Brno, Czech Republic, 24/08/98. https://doi.org/10.1007/BFb0055822

Degree-preserving forests. / Broersma, Hajo; Huck, Andreas; Kloks, Ton et al.
Mathematical Foundations of Computer Science 1998: 23rd International Symposium, MFCS'98 Brno, Czech Republic, August 24–28, 1998, Proceedings. ed. / Luboš Brim; Jozef Gruska; Jiří Zlatuška. Berlin, Heidelberg: Springer, 1998. p. 713-721 (Lecture Notes in Computer Science; Vol. 1450).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

TY - CHAP

T1 - Degree-preserving forests

AU - Broersma, Hajo

AU - Huck, Andreas

AU - Kloks, Ton

AU - Koppius, Otto

AU - Kratsch, Dieter

AU - Müller, Haiko

AU - Tuinstra, Hilde

N1 - Conference code: 23

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 - Span tree

KW - Planar graph

KW - Interval graph

KW - Chordal graph

KW - Linear time algorithm

U2 - 10.1007/BFb0055822

DO - 10.1007/BFb0055822

M3 - Chapter

SN - 978-3-540-64827-7

T3 - Lecture Notes in Computer Science

SP - 713

EP - 721

BT - Mathematical Foundations of Computer Science 1998

A2 - Brim, Luboš

A2 - Gruska, Jozef

A2 - Zlatuška, Jiří

PB - Springer

CY - Berlin, Heidelberg

T2 - 23rd International Symposium on Mathematical Foundations of Computer Science, MFCS 1998

Y2 - 24 August 1998 through 28 August 1998

ER -

Broersma H, Huck A, Kloks T, Koppius O, Kratsch D, Müller H et al. Degree-preserving forests. In Brim L, Gruska J, Zlatuška J, editors, Mathematical Foundations of Computer Science 1998: 23rd International Symposium, MFCS'98 Brno, Czech Republic, August 24–28, 1998, Proceedings. Berlin, Heidelberg: Springer. 1998. p. 713-721. (Lecture Notes in Computer Science). doi: 10.1007/BFb0055822

Degree-preserving forests

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Research output

Degree-preserving forests

Cite this