### Abstract

Original language | Undefined |
---|---|

Title of host publication | Mathematical Foundations of Computer Science : 23rd International Symposium, MFCS '98 |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 713-721 |

Number of pages | 10 |

ISBN (Print) | 3-540-64827-5 |

DOIs | |

Publication status | Published - 1998 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Number | 1450 |

Volume | 1450 |

ISSN (Print) | 0302-9743 |

### Keywords

- METIS-141078
- IR-92413

### Cite this

*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

}

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

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

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 -