An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs

DOI10.1007/s00453-013-9765-4zbMath1303.05186OpenAlexW2012939398MaRDI QIDQ472490

Ekkehard Köhler, Feodor F. Dragan

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9765-4

zbMATH Keywords

graph algorithmsapproximation algorithmsbalanced separatorsgeneralized chordal graphsminimum max-stretch spanning tree problemRobertson-Seymour's tree-decompositiontree \(t\)-spanner problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

On approximating tree spanners that are breadth first search trees ⋮ Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \) ⋮ Computing the union join and subset graph of acyclic hypergraphs in subquadratic time ⋮ Injective hulls of various graph classes ⋮ 3-colouring for dually chordal graphs and generalisations ⋮ Helly-gap of a graph and vertex eccentricities ⋮ Treelength of series-parallel graphs ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Tree spanners of bounded degree graphs ⋮ On Strong Tree-Breadth ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ A short note on the complexity of computing strong pathbreadth ⋮ On the complexity of computing treebreadth ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ On the Complexity of Computing Treebreadth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating \(k\)-spanner problems for \(k>2\)
• Chordality properties on graphs and minimal conceptual connections in semantic data models
• Spanners in sparse graphs
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
• Dynamic analysis of the arrow distributed protocol
• Tree spanners for bipartite graphs and probe interval graphs
• On the complexity of computing treelength
• A note on distance approximating trees in graphs
• Low complexity variants of the arrow distributed directory
• A characterisation of rigid circuit graphs
• Tree spanners on chordal graphs: complexity and algorithms
• Tree-decompositions with bags of small diameter
• Spanners for bounded tree-length graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• The zoo of tree spanner problems
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• On the Desirability of Acyclic Database Schemes
• An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
• A Separator Theorem for Chordal Graphs
• Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Lower-Stretch Spanning Trees
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Graph Classes: A Survey
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Additive Tree Spanners
• Tree Spanners
• Tree spanners in planar graphs

This page was built for publication: An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs