A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

DOI10.1016/S1570-8667(03)00007-8MaRDI QIDQ876695zbMATH OpenFDO

Authors W. Duckworth, Nicholas Wormald, Michele Zito

Publication date 26 April 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

zbMATH Keywords

triangulationplanarpolynomial time approximation scheme4-connected2-spanner

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Distance in graphs (05C12)

Recommendations

• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• Approximation of minimum weight spanners for sparse graphs
• scientific article; zbMATH DE number 1375574
• Generating Sparse 2-Spanners
• NP-hardness and fixed-parameter tractability of the minimum spanner problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 1107724 (Why is no real title available?)
• scientific article; zbMATH DE number 1182768 (Why is no real title available?)
• An Optimal Synchronizer for the Hypercube
• Approximation algorithms for NP-complete problems on planar graphs
• Graph spanners
• NP-completeness of minimum spanner problems
• NP-completeness of some generalizations of the maximum matching problem
• On sparse spanners of weighted graphs
• Relations between packing and covering numbers of a tree
• Spanners in graphs of bounded degree
• Sparse hypercube 3-spanners

Cited in

(6)

• Spanners in sparse graphs
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• Approximation of minimum weight spanners for sparse graphs
• On the approximability of the maximum induced matching problem

This page was built for publication: A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

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