𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Degree-preserving trees

✍ Scribed by Broersma, Hajo; Koppius, Otto; Tuinstra, Hilde; Huck, Andreas; Kloks, Ton; Kratsch, Dieter; M�ller, Haiko

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
186 KB
Volume
35
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the degree-preserving spanning tree (DPST) problem: Given a connected graph G G G, find a spanning tree T T T of G G G such that as many vertices of T T T as possible have the same degree in T T T as in G G 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 O O(n n n 4 ) algorithm. Furthermore, we present linear time approximation algorithms for planar graphs of a worst-case performance ratio of 1for every > 0.

📜 SIMILAR VOLUMES

Tree codes that preserve increases and d
Tree codes that preserve increases and degree sequences
✍ G. Kreweras; P. Moszkowski 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 292 KB

Kreweras, G. and P. Moszkowski, Tree codes that preserve increases and degree sequences, Discrete Mathematics 87 (1991) 291-296. We define a bijection from the set .Y,, of rooted Cayley's trees with n vertices to the set [l, n]"-' of words of n -1 letters written with the alphabet [l, n]. This code

The degree-preserving spanning tree prob
The degree-preserving spanning tree problem in strongly chordal and directed path graphs
✍ Ching-Chi Lin; Gerard J. Chang; Gen-Huey Chen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract Suppose __G__ is a connected graph and __T__ a spanning tree of __G__. A vertex __v__ ε __V__(__G__) is said to be a degree‐preserving vertex if its degree in __T__ is the same as its degree in __G__. The degree‐preserving spanning tree problem is to find a spanning tree __T__ of a conn

Degrees of Souslin Trees
Degrees of Souslin Trees
✍ Stefan Bilaniuk 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 692 KB
A spanning tree of the 2m-dimensional hy
A spanning tree of the 2m-dimensional hypercube with maximum number of degree-preserving vertices
✍ Sul-young Choi; Puhua Guan 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 190 KB

For an n-dimensional hypercube Q., the maximum number of degree-preserving vertices in a spanning tree is 2"jn if n = 2" for an integer M. (If n # 2", then the maximum number of degree-preserving vertices in a spanning tree is less than 2"/n.) We also construct a spanning tree of Qzm with maximum nu

A note on graphs with diameter-preservin
A note on graphs with diameter-preserving spanning trees
✍ Fred Buckley; Martin Lewinter 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th