Approximation of minimum weight spanners for sparse graphs
type: Item
instance of: scholarly article
title: Approximation of minimum weight spanners for sparse graphs
zbMATH Open document ID: 1206.68232
author: Feodor F. Dragan
author: Fedor V. Fomin
author: Petr A. Golovach
published in: Theoretical Computer Science
publication date: 2011-02-21T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5853816
zbMATH Keywords: graph algorithms
zbMATH Keywords: graph spanners
zbMATH Keywords: sparsest \(t\)-spanner
zbMATH Keywords: EPTAS
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.11.034
OpenAlex ID: W2126121312
Wikidata QID: Q60488549
cites work: On sparse spanners of weighted graphs
cites work: Easy problems for tree-decomposable graphs
cites work: Complexity of network synchronization
cites work: Routing with Polynomial Communication-Space Trade-Off
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Q3836515
cites work: Tree Spanners
cites work: On the efficiency of polynomial time approximation schemes
cites work: There are planar graphs almost as good as the complete graph
cites work: Delaunay graphs are almost as good as complete graphs
cites work: Spanners in Sparse Graphs
cites work: A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
cites work: A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
cites work: Computing almost shortest paths
cites work: The hardness of approximating spanner problems
cites work: Approximating \(k\)-spanner problems for \(k>2\)
cites work: Q4886099
cites work: Diameter and treewidth in minor-closed graph families
cites work: Local tree-width, excluded minors, and approximation algorithms
cites work: Treewidth. Computations and approximations
cites work: On the hardness of approximating spanners
cites work: Generating Sparse 2-Spanners
cites work: Geometric Spanner Networks
cites work: Graph spanners
cites work: A trade-off between space and efficiency for routing tables
cites work: An Optimal Synchronizer for the Hypercube
cites work: Low Distortion Spanners
cites work: Graph minors. III. Planar tree-width
cites work: Automata, Languages and Programming
cites work: Approximate distance oracles
DOI: 10.1016/J.TCS.2010.11.034
description: scientific article; zbMATH DE number 5853816