𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tree spanners on chordal graphs: complexity and algorithms

✍ Scribed by Andreas Brandstädt; Feodor F. Dragan; Hoàng-Oanh Le; Van Bang Le

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
329 KB
Volume
310
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The TREE t-SPANNER problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359 -387) by showing that, for any t ¿ 4, TREE t-SPANNER is NP-complete even on chordal graphs of diameter at most t + 1 (if t is even), respectively, at most t + 2 (if t is odd). Then we point out that every chordal graph of diameter at most t -1 (respectively, t -2) admits a tree t-spanner whenever t ¿ 2 is even (respectively, t ¿ 3 is odd), and such a tree spanner can be constructed in linear time.

The complexity status of TREE 3-SPANNER still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide TREE 3-SPANNER e ciently.

📜 SIMILAR VOLUMES

Tree-decompositions, tree-representabili
Tree-decompositions, tree-representability and chordal graphs
✍ Reinhard Diestel 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 427 KB

The following assertions are shown to be equivalent, for any countable graph G: (1) G can be represented as the intersection graph of a family of subtrees of a tree; (2) G admits a tree-decomposition (Robertson/Seymour) into primes; (3) G is chordal, and G admits a simpkial tree-decomposition (Halin

Distance Approximating Trees for Chordal
Distance Approximating Trees for Chordal and Dually Chordal Graphs
✍ Andreas Brandstädt; Victor Chepoi; Feodor Dragan 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 165 KB

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 d