Tree spanners of bounded degree graphs

DOI10.1016/j.dam.2017.10.025zbMath1377.05036arXiv1503.06822OpenAlexW1796769919MaRDI QIDQ1693164

Ioannis Papoutsakis

Publication date: 11 January 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

distancespanning treetree spannerbounded degree graphefficient graph algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items (4)

On approximating tree spanners that are breadth first search trees ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Tree spanners of bounded degree graphs ⋮ Spanning trees with disjoint dominating and 2-dominating sets

Cites Work

• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• On approximating tree spanners that are breadth first search trees
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Tree \(t\)-spanners in outerplanar graphs via supply demand partition
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Trigraphs
• Restrictions of minimum spanner problems
• 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
• Spanners in Sparse Graphs
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Complexity of network synchronization
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Optimal tree 3-spanners in directed path graphs
• Additive Tree Spanners
• Planar spanners and approximate shortest path queries among obstacles in the plane
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Graph-Theoretic Concepts in Computer Science
• A tight bound on approximating arbitrary metrics by tree metrics
• Tree spanners in planar graphs

This page was built for publication: Tree spanners of bounded degree graphs