Tree spanners on chordal graphs: complexity and algorithms
type: Item
instance of: scholarly article
title: Tree spanners on chordal graphs: complexity and algorithms
zbMATH Open document ID: 1049.05075
DOI: 10.1016/S0304-3975(03)00424-9
author: Andreas Brandstädt
author: Feodor F. Dragan
author: Hoàng-Oanh Le
author: Van Bang Le
published in: Theoretical Computer Science
publication date: 2004-10-27T00:00:00Z
review text: A spanning tree \(T\) of a graph \(G\) is called \(t\)-multiplicative tree spanner (tree \(t\)-spanner for short) if \(d_T(u,v) \leq t \cdot d_G(u,v)\) holds for all vertices \(u\) and \(v\). The tree \(t\)-spanner problem asks whether a graph admits a tree \(t\)-spanner. Strengthening a result by \textit{L. Cai} and \textit{D. G. Corneil} [SIAM J. Discrete Math. 8, No. 3, 359--387 (1995; Zbl 0832.05037)] it is shown that, for any \(t \geq 4\), the tree \(t\)-spanner problem is NP-complete when restricted to chordal graphs of diameter at most \(2\lceil t/2\rceil+1\). For \(t \geq 2\), if every chordal graph of diameter at most \(2\lfloor t/2\rfloor-1\) has a tree \(t\)-spanner then it can be constructed in linear time. Restrictions to subclasses of chordal graphs are considered as well.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 2111061
zbMATH Keywords: tree spanner
zbMATH Keywords: chordal graph
zbMATH Keywords: distance
zbMATH Keywords: spanning tree
zbMATH Keywords: NP-completeness
zbMATH Keywords: graph algorithm
MaRDI profile type: Publication
cites work: Reconstructing the shape of a tree from observed dissimilarity data
cites work: Distance Approximating Trees for Chordal and Dually Chordal Graphs
cites work: Graph Classes: A Survey
cites work: Q3139523
cites work: Tree Spanners
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Centers of triangulated graphs
cites work: Q4942657
cites work: Characterizations of strongly chordal graphs
cites work: Convexity in Graphs and Hypergraphs
cites work: Tree spanners in planar graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3328583
cites work: Optimal tree 3-spanners in directed path graphs
cites work: A characterization of ptolemaic graphs
cites work: Tree 3-spanners on interval, permutation and regular bipartite graphs
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: Graph spanners
cites work: Distance approximating spanning trees
cites work: Q3139291
cites work: Restrictions of minimum spanner problems
cites work: Q3691771
full work available at URL: s0304-3975(03)00424-9
OpenAlex ID: W2169648807
description: scientific article; zbMATH DE number 2111061