### Abstract

Original language | Undefined |
---|---|

Pages (from-to) | 58-66 |

Number of pages | 9 |

Journal | Theoretical computer science |

Volume | 571 |

DOIs | |

Publication status | Published - Mar 2015 |

### Keywords

- EWI-25791
- MSC-05C
- Unit disk graph
- Vertex cover
- P3 cover
- PTAS
- c-Local problem
- Minimum weight cover
- Grid graph
- METIS-312513
- IR-94682
- Connected cover

### Cite this

*Theoretical computer science*,

*571*, 58-66. https://doi.org/10.1016/j.tcs.2015.01.005

}

*Theoretical computer science*, vol. 571, pp. 58-66. https://doi.org/10.1016/j.tcs.2015.01.005

**A PTAS for the minimum weight connected vertex cover P3 problem on unit disk graphs.** / Wang, Limin; Zhang, Xiaoyan; Zhang, X.; Zhang, Zhao; Broersma, Haitze J.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - A PTAS for the minimum weight connected vertex cover P3 problem on unit disk graphs

AU - Wang, Limin

AU - Zhang, Xiaoyan

AU - Zhang, X.

AU - Zhang, Zhao

AU - Broersma, Haitze J.

N1 - eemcs-eprint-25791

PY - 2015/3

Y1 - 2015/3

N2 - Let G =(V, E) be a weighted graph, i.e., with a vertex weight function w :V→R+. We study the problem of determining a minimum weight connected subgraph of G that has at least one vertex in common with all paths of length two in G. It is known that this problem is NP-hard for general graphs. We first show that it remains NP-hard when restricted to unit disk graphs. Our main contribution is a polynomial time approximation scheme for this problem if we assume that the problem is c-local and the unit disk graphs have minimum degree of at least two.

AB - Let G =(V, E) be a weighted graph, i.e., with a vertex weight function w :V→R+. We study the problem of determining a minimum weight connected subgraph of G that has at least one vertex in common with all paths of length two in G. It is known that this problem is NP-hard for general graphs. We first show that it remains NP-hard when restricted to unit disk graphs. Our main contribution is a polynomial time approximation scheme for this problem if we assume that the problem is c-local and the unit disk graphs have minimum degree of at least two.

KW - EWI-25791

KW - MSC-05C

KW - Unit disk graph

KW - Vertex cover

KW - P3 cover

KW - PTAS

KW - c-Local problem

KW - Minimum weight cover

KW - Grid graph

KW - METIS-312513

KW - IR-94682

KW - Connected cover

U2 - 10.1016/j.tcs.2015.01.005

DO - 10.1016/j.tcs.2015.01.005

M3 - Article

VL - 571

SP - 58

EP - 66

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

ER -