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

DOI10.1007/978-3-540-85238-4_23zbMath1173.68602OpenAlexW1480517702WikidataQ60488715 ScholiaQ60488715MaRDI QIDQ3599135

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

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)

Related Items (3)

Approximation of minimum weight spanners for sparse graphs ⋮ Spanners of bounded degree graphs ⋮ Spanners in sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating \(k\)-spanner problems for \(k>2\)
• Delaunay graphs are almost as good as complete graphs
• 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
• Diameter and treewidth in minor-closed graph families
• There are planar graphs almost as good as the complete graph
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Easy problems for tree-decomposable graphs
• Geometric Spanner Networks
• Spanners in Sparse Graphs
• Approximate distance oracles
• 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
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph Drawing
• Computing almost shortest paths
• On the hardness of approximating spanners

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