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

被引：12

作者：

Wang, Limin ^{[1
,2
]}

Zhang, Xiaoyan ^{[1
,2
,3
]}

Zhang, Zhao ^{[4
]}

Broersma, Hajo ^{[3
]}

机构：

[1] Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China

[2] Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China

[3] Univ Twente, Fac Elect Engn Math & Comp Sci, NL-7500 AE Enschede, Netherlands

[4] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua, Zhejiang, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2015年 / 571卷

关键词：

PTAS; Vertex cover; P-3; cover; Minimum weight cover; Connected cover; c-Local problem; Unit disk graph; Grid graph;

D O I：

10.1016/j.tcs.2015.01.005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：58 / 66

页数：9

共 16 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

Bondy J.A., 2008, GRAD TEXTS MATH, V244

[3]

Byrka J, 2010, ACM S THEORY COMPUT, P583

[4] PTAS for minimum weighted connected vertex cover problem with c-local condition in unit disk graphs [J].

Fan, Lidan ;

Zhang, Zhao ;

Wang, Wei .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011, 22 (04) :663-673

[5] On approximability of the independent/connected edge dominating set problems [J].

Fujito, T .

INFORMATION PROCESSING LETTERS, 2001, 79 (06) :261-266

[6] RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :826-834

[7]

Kratochvil J., 1997, Graph Drawing. Symposium on Graph Drawing, GD '96. Proceedings, P257

[8] PTAS for the minimum k-path connected vertex cover problem in unit disk graphs [J].

Liu, Xianliang ;

Lu, Hongliang ;

Wang, Wei ;

Wu, Weili .

JOURNAL OF GLOBAL OPTIMIZATION, 2013, 56 (02) :449-458

[9]

Menezes A., 1996, HDB APPL CRYPTOGRAPH

[10]

Novotny M, 2010, LECT NOTES COMPUT SC, V6033, P106, DOI 10.1007/978-3-642-12368-9_8

← 1 2 →