Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10898-011-9831-x | J. Global Optimization |
Keywords | Field | DocType |
PTAS,k-Path connected vertex cover,Unit disk graph | Discrete mathematics,Combinatorics,Edge cover,Vertex (graph theory),Neighbourhood (graph theory),Vertex separator,Connected component,Vertex cover,Strongly connected component,Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
56 | 2 | 0925-5001 |
Citations | PageRank | References |
15 | 0.73 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xianliang Liu | 1 | 15 | 1.07 |
| Hongliang Lu | 2 | 26 | 10.07 |
| Wei Wang | 3 | 81 | 12.64 |
| Weili Wu | 4 | 2093 | 170.29 |