A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
type: Item
instance of: scholarly article
title: A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
zbMATH Open document ID: 1118.05313
DOI: 10.1016/S1570-8667(03)00007-8
author: W. Duckworth
author: Nicholas Wormald
author: Michele Zito
published in: Journal of Discrete Algorithms
publication date: 2007-04-26T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5147080
zbMATH Keywords: 2-spanner
zbMATH Keywords: 4-connected
zbMATH Keywords: planar
zbMATH Keywords: triangulation
zbMATH Keywords: polynomial time approximation scheme
MaRDI profile type: Publication
cites work: On sparse spanners of weighted graphs
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Q4373672
cites work: NP-completeness of minimum spanner problems
cites work: Spanners in graphs of bounded degree
cites work: Q4342632
cites work: Sparse hypercube 3-spanners
cites work: Q4198056
cites work: Q4400851
cites work: Relations between packing and covering numbers of a tree
cites work: Graph spanners
cites work: An Optimal Synchronizer for the Hypercube
cites work: NP-completeness of some generalizations of the maximum matching problem
description: scientific article; zbMATH DE number 5147080