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

Limin Wang, Xiaoyan Zhang, X. Zhang, Zhao Zhang, Haitze J. Broersma

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

Abstract

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.
Original languageUndefined
Pages (from-to)58-66
Number of pages9
JournalTheoretical computer science
Volume571
DOIs
Publication statusPublished - 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