Approximation of minimum weight spanners for sparse graphs

DOI10.1016/J.TCS.2010.11.034MaRDI QIDQ627187zbMATH OpenOpenAlexWikidataFDO

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

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 algorithmsgraph spannersEPTASsparsest \(t\)-spanner

Mathematics Subject Classification ID

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

Recommendations

• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• Spanners in Sparse Graphs
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
• Spanners in sparse graphs
• NP-hardness and fixed-parameter tractability of the minimum spanner problem

Cites work

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

Cited in

(9)

• Parameterized complexity of the spanning tree congestion problem
• Minimum fill-in of sparse graphs: kernelization and approximation
• Spanners in sparse graphs
• An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
• scientific article; zbMATH DE number 2119747 (Why is no real title available?)
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q627187)