Approximation of minimum weight spanners for sparse graphs

DOI10.1016/j.tcs.2010.11.034zbMath1206.68232OpenAlexW2126121312WikidataQ60488549 ScholiaQ60488549MaRDI QIDQ627187

Fedor V. Fomin, Petr A. Golovach, Feodor F. Dragan

Publication date: 21 February 2011

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.034

zbMATH Keywords

graph spannersgraph algorithmsEPTASsparsest \(t\)-spanner

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (2)

Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Parameterized complexity of the spanning tree congestion problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the efficiency of polynomial time approximation schemes
• Approximating \(k\)-spanner problems for \(k>2\)
• Delaunay graphs are almost as good as complete graphs
• Graph minors. III. Planar tree-width
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
• On sparse spanners of weighted graphs
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• Diameter and treewidth in minor-closed graph families
• There are planar graphs almost as good as the complete graph
• The hardness of approximating spanner problems
• Local tree-width, excluded minors, and approximation algorithms
• Easy problems for tree-decomposable graphs
• Geometric Spanner Networks
• Spanners in Sparse Graphs
• Approximate distance oracles
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• Complexity of network synchronization
• Graph spanners
• Routing with Polynomial Communication-Space Trade-Off
• Approximation algorithms for NP-complete problems on planar graphs
• Generating Sparse 2-Spanners
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Low Distortion Spanners
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Automata, Languages and Programming
• Computing almost shortest paths
• On the hardness of approximating spanners

This page was built for publication: Approximation of minimum weight spanners for sparse graphs