A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
From MaRDI portal
Publication:876695
DOI10.1016/S1570-8667(03)00007-8zbMATH Open1118.05313MaRDI QIDQ876695FDOQ876695
Nicholas Wormald, Michele Zito, W. Duckworth
Publication date: 26 April 2007
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Distance in graphs (05C12)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for NP-complete problems on planar graphs
- An Optimal Synchronizer for the Hypercube
- On sparse spanners of weighted graphs
- Graph spanners
- Spanners in graphs of bounded degree
- NP-completeness of some generalizations of the maximum matching problem
- Relations between packing and covering numbers of a tree
- NP-completeness of minimum spanner problems
- 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)
