Tree spanners on chordal graphs: complexity and algorithms

DOI10.1016/S0304-3975(03)00424-9zbMath1049.05075OpenAlexW2169648807MaRDI QIDQ1884978

Hoàng-Oanh Le, Feodor F. Dragan, Andreas Brandstädt, Van Bang Le

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00424-9

zbMATH Keywords

graph algorithmdistanceNP-completenessspanning treechordal graphtree spanner

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (25)

On approximating tree spanners that are breadth first search trees ⋮ Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs ⋮ Tree-decompositions with bags of small diameter ⋮ Well-partitioned chordal graphs ⋮ Spanners for bounded tree-length graphs ⋮ Optimality computation of the minimum stretch spanning tree problem ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Tree spanners of bounded degree graphs ⋮ Hardness and efficiency on minimizing maximum distances in spanning trees ⋮ Three problems on well-partitioned chordal graphs ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Spanners in sparse graphs ⋮ Hardness and efficiency on \(t\)-admissibility for graph operations ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ The zoo of tree spanner problems ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Rooted directed path graphs are leaf powers ⋮ Network flow spanners ⋮ Complexity Results for the Spanning Tree Congestion Problem ⋮ The minimum stretch spanning tree problem for typical graphs ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ Tree 3-Spanner in 2-sep Chordal Graphs: Characterization, Recognition, and Construction. ⋮ Fast Diameter Computation within Split Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Centers of triangulated graphs
• Characterizations of strongly chordal graphs
• Restrictions of minimum spanner problems
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Convexity in Graphs and Hypergraphs
• Graph spanners
• A characterization of ptolemaic graphs
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Graph Classes: A Survey
• Optimal tree 3-spanners in directed path graphs
• Distributed Computing: A Locality-Sensitive Approach
• Tree Spanners
• Distance approximating spanning trees
• Tree spanners in planar graphs

This page was built for publication: Tree spanners on chordal graphs: complexity and algorithms