PTAS for connected vertex cover in unit disk graphs
type: Item
instance of: scholarly article
title: PTAS for connected vertex cover in unit disk graphs
zbMATH Open document ID: 1192.68495
author: Zhao Zhang
author: Xiaofeng Gao
author: Weili Wu
published in: Theoretical Computer Science
publication date: 2009-11-25T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 5638317
zbMATH Keywords: PTAS
zbMATH Keywords: connected vertex cover
zbMATH Keywords: unit disk graph
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.01.035
OpenAlex ID: W2017106977
cites work: Approximating the tree and tour covers of a graph
cites work: Q3221758
cites work: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
cites work: Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
cites work: A 2-approximation NC algorithm for connected vertex cover and tree cover
cites work: `` Strong '' NP-Completeness Results
cites work: Q3002852
cites work: Q4142699
cites work: Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks
cites work: Ramsey numbers and an approximation algorithm for the vertex cover problem
cites work: Optimization, approximation, and complexity classes
cites work: Depth-first search and the vertex cover problem
cites work: An approximation scheme for some Steiner tree problems in the plane
DOI: 10.1016/J.TCS.2009.01.035
Recommended article: PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
Recommended article: A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
Recommended article: PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
Recommended article: Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
Recommended article: A PTAS for the Weighted Unit Disk Cover Problem
Recommended article: Approximation and Online Algorithms
Recommended article: On approximability of connected path vertex cover
Recommended article: \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
description: scientific article; zbMATH DE number 5638317