Name
Abstract | ||
|---|---|---|
AbstractGiven a connected graph $$G=(V,E)$$G=(V,E), the Connected Vertex Cover (CVC) problem is to find a vertex set $$S\subset V$$S?V with minimum cardinality such that every edge is incident to a vertex in S, and moreover, the induced graph G[S] is connected. In this paper, we investigate the CVC problem in k-regular graphs for any fixed k ($$k\ge 4$$k?4). First, we prove that the CVC problem is NP-hard for k-regular graphs,and then we give a lower bound for the minimum size of a CVC, based on which, we propose a $$\frac{2k}{k+2}+O(\frac{1}{n})$$2kk+2+O(1n)-approximation algorithm for the CVC problem. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s10878-019-00403-3 | Periodicals |
Keywords | Field | DocType |
Connected vertex cover problem,Approximation algorithm,k-Regular graph | Graph,Approximation algorithm,Combinatorics,Vertex (geometry),Upper and lower bounds,Cardinality,Regular graph,Vertex cover,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 2 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuchao Li | 1 | 0 | 0.34 |
| Wei Wang | 2 | 81 | 12.64 |
| Zishen Yang | 3 | 2 | 1.04 |