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

  • 6 Citations

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
StatePublished - Mar 2015

Fingerprint

Computational complexity
Polynomials

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

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

In: Theoretical computer science, Vol. 571, 03.2015, p. 58-66.

Research output: Scientific - peer-reviewArticle

@article{d3aa20fa45a1450e86d8c287fc11ffca,
title = "A PTAS for the minimum weight connected vertex cover P3 problem on unit disk graphs",
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.",
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",
author = "Limin Wang and Xiaoyan Zhang and X. Zhang and Zhao Zhang and Broersma, {Haitze J.}",
note = "eemcs-eprint-25791",
year = "2015",
month = "3",
doi = "10.1016/j.tcs.2015.01.005",
volume = "571",
pages = "58--66",
journal = "Theoretical computer science",
issn = "0304-3975",
publisher = "Elsevier",

}

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.

In: Theoretical computer science, Vol. 571, 03.2015, p. 58-66.

Research output: Scientific - peer-reviewArticle

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

T2 - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

ER -