On approximating tree spanners that are breadth first search trees

DOI10.1016/j.jcss.2016.02.008zbMath1338.68222arXiv1506.02243OpenAlexW2287355843MaRDI QIDQ269500

Ioannis Papoutsakis

Publication date: 18 April 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.02243

zbMATH Keywords

distancespanning treehardness of approximationlow stretchtree spanner

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

Tree spanners of bounded degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Trigraphs
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Low complexity variants of the arrow distributed directory
• Tree spanners of bounded degree graphs
• There are planar graphs almost as good as the complete graph
• Tree spanners on chordal graphs: complexity and algorithms
• Spanners of bounded degree graphs
• Geometric Spanner Networks
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Complexity of network synchronization
• Planar spanners and approximate shortest path queries among obstacles in the plane
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• A tight bound on approximating arbitrary metrics by tree metrics
• Tree spanners in planar graphs

This page was built for publication: On approximating tree spanners that are breadth first search trees