A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
From MaRDI portal
Publication:876695
DOI10.1016/S1570-8667(03)00007-8zbMath1118.05313MaRDI QIDQ876695
Nicholas C. Wormald, Michele Zito, William Duckworth
Publication date: 26 April 2007
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
Approximation of minimum weight spanners for sparse graphs ⋮ Spanners in sparse graphs ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ On the approximability of the maximum induced matching problem ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- NP-completeness of minimum spanner problems
- Sparse hypercube 3-spanners
- Graph spanners
- Approximation algorithms for NP-complete problems on planar graphs
- Spanners in graphs of bounded degree
- An Optimal Synchronizer for the Hypercube
This page was built for publication: A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
