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

Limin Wang; Xiaoyan Zhang; Zhao Zhang; Hajo Broersma

doi:10.1016/j.tcs.2015.01.005

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

Limin Wang, Xiaoyan Zhang, Zhao Zhang, Hajo Broersma

Discrete Mathematics and Mathematical Programming

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

13 Citations (Scopus)

52 Downloads (Pure)

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 language	English
Pages (from-to)	58-66
Number of pages	9
Journal	Theoretical computer science
Volume	571
DOIs	https://doi.org/10.1016/j.tcs.2015.01.005
Publication status	Published - Mar 2015

Keywords

MSC-05C
Unit disk graph
Vertex cover
P3 cover
PTAS
c-Local problem
Minimum weight cover
Grid graph
Connected cover
2023 OA procedure

Access to Document

10.1016/j.tcs.2015.01.005

ArticleFinal published version, 339 KBLicence: Taverne

Cite this

@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 = "MSC-05C, Unit disk graph, Vertex cover, P3 cover, PTAS, c-Local problem, Minimum weight cover, Grid graph, Connected cover, 2023 OA procedure",

author = "Limin Wang and Xiaoyan Zhang and Zhao Zhang and Hajo Broersma",

note = "eemcs-eprint-25791 ",

year = "2015",

month = mar,

doi = "10.1016/j.tcs.2015.01.005",

language = "English",

volume = "571",

pages = "58--66",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

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, Zhao

AU - Broersma, Hajo

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 - 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 - Connected cover

KW - 2023 OA procedure

U2 - 10.1016/j.tcs.2015.01.005

DO - 10.1016/j.tcs.2015.01.005

M3 - Article

SN - 0304-3975

VL - 571

SP - 58

EP - 66

JO - Theoretical computer science

JF - Theoretical computer science

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this