A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs

DOI10.1007/978-3-540-85238-4_23MaRDI QIDQ3599135zbMATH OpenOpenAlexWikidataFDO

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

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximation of minimum weight spanners for sparse 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 1629828 (Why is no real title available?)
• scientific article; zbMATH DE number 1670859 (Why is no real title available?)
• 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 2-spanner of 4-connected planar triangulations
• A partial k-arboretum of graphs with bounded treewidth
• 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
• 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
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Generating Sparse 2-Spanners
• Geometric Spanner Networks
• Graph Drawing
• Graph spanners
• On sparse spanners of weighted graphs
• On the hardness of approximating spanners
• Routing with Polynomial Communication-Space Trade-Off
• Spanners in Sparse Graphs
• There are planar graphs almost as good as the complete graph
• Tree Spanners

Cited in

(6)

• Spanners in sparse graphs
• An FPT Algorithm for Minimum Additive Spanner Problem.
• scientific article; zbMATH DE number 2119747 (Why is no real title available?)
• Spanners of bounded degree graphs
• Approximation of minimum weight spanners for sparse graphs
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

This page was built for publication: A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs

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