Spanners of bounded degree graphs
From MaRDI portal
Publication:1944059
DOI10.1016/j.ipl.2010.10.021zbMath1260.68154OpenAlexW2029105149WikidataQ60488581 ScholiaQ60488581MaRDI QIDQ1944059
Erik Jan van Leeuwen, Fedor V. Fomin, Petr A. Golovach
Publication date: 4 April 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2010.10.021
Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On approximating tree spanners that are breadth first search trees ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Optimality computation of the minimum stretch spanning tree problem ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Tree spanners of bounded degree graphs ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ The minimum stretch spanning tree problem for typical graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A special planar satisfiability problem and a consequence of its NP- completeness
- Treewidth. Computations and approximations
- Minimal congestion trees
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Competitive concurrent distributed queuing
- Complexity Results for the Spanning Tree Congestion Problem
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Lower-Stretch Spanning Trees
- Graph spanners
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A tight bound on approximating arbitrary metrics by tree metrics
- Tree spanners in planar graphs
