PTAS for the minimum k-path connected vertex cover problem in unit disk graphs

Xianliang Liu, Hongliang Lu, Wei Wang () and Weili Wu

Journal of Global Optimization, 2013, vol. 56, issue 2, 449-458

Abstract: In the Minimum k-Path Connected Vertex Cover Problem (MkPCVCP), we are given a connected graph G and an integer k ≥ 2, and are required to find a subset C of vertices with minimum cardinality such that each path with length k − 1 has a vertex in C, and moreover, the induced subgraph G[C] is connected. MkPCVCP is a generalization of the minimum connected vertex cover problem and has applications in many areas such as security communications in wireless sensor networks. MkPCVCP is proved to be NP-complete. In this paper, we give the first polynomial time approximation scheme (PTAS) for MkPCVCP in unit disk graphs, for every fixed k ≥ 2. Copyright Springer Science+Business Media, LLC. 2013

Keywords: PTAS; k-Path connected vertex cover; Unit disk graph (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-011-9831-x (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:56:y:2013:i:2:p:449-458

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-011-9831-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().