𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Distance Approximating Trees for Chordal and Dually Chordal Graphs

✍ Scribed by Andreas Brandstädt; Victor Chepoi; Feodor Dragan

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
165 KB
Volume
30
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we show that, for each chordal graph G, there is a tree T such that T is a spanning tree of the square G 2 of G and, for every two vertices, the distance between them in T is not larger than the distance in G plus 2. Moreover, we prove that, if G is a strongly chordal graph or even a dually chordal graph, then there exists a spanning tree T of G that is an additive 3-spanner as well as a multiplicative 4-spanner of G. In all cases the tree T can be computed in linear time.

📜 SIMILAR VOLUMES

Improved Bandwidth Approximation for Tre
Improved Bandwidth Approximation for Trees and Chordal Graphs
✍ Anupam Gupta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 110 KB

A linear arrangement of an n-vertex graph G = V E is a one-one mapping f of the vertex set V onto the set n = 0 1 n -1 . The bandwidth of this linear arrangement is the maximum difference between the images of the endpoints of any edge in E G . When the input graph G is a tree, the best known approx

Strong clique trees, neighborhood trees,
Strong clique trees, neighborhood trees, and strongly chordal graphs
✍ McKee, Terry A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationsh

Complexity of approximating the oriented
Complexity of approximating the oriented diameter of chordal graphs
✍ Fedor V. Fomin; Martín Matamala; Ivan Rapaport 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract The oriented diameter of a bridgeless connected undirected (__bcu__) graph __G__ is the smallest diameter among all the diameters of strongly connected orientations of __G__. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐

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

A linear-time algorithm for connectedr-d
A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
✍ Brandst�dt, Andreas; Dragan, Feodor F. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree