NP-completeness and APX-completeness of restrained domination in graphs

Lei Chen; Weiming Zeng; Changhong Lu

doi:10.1016/j.tcs.2012.05.005

NP-completeness and APX-completeness of restrained domination in graphs

Lei Chen
, Weiming Zeng
, Changhong Lu^*

^*此作品的通讯作者

数学科学学院

Shanghai Maritime University

科研成果: 期刊稿件 › 文章 › 同行评审

9 引用（Scopus）

摘要

Let G=(V,E) be a simple graph. A vertex set S⊆V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V-S. In this paper, we investigate the NP-completeness of the restrained domination problem in planar graphs and split graphs. Meanwhile, it is proved that the restrained domination problem is APX-complete for bounded-degree graphs.

源语言	英语
页（从-至）	1-8
页数	8
期刊	Theoretical Computer Science
卷	448
DOI	https://doi.org/10.1016/j.tcs.2012.05.005
出版状态	已出版 - 24 8月 2012

访问文件

10.1016/j.tcs.2012.05.005

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{0b20c405c2074aaf988f66cad10d42e4,

title = "NP-completeness and APX-completeness of restrained domination in graphs",

abstract = "Let G=(V,E) be a simple graph. A vertex set S⊆V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V-S. In this paper, we investigate the NP-completeness of the restrained domination problem in planar graphs and split graphs. Meanwhile, it is proved that the restrained domination problem is APX-complete for bounded-degree graphs.",

keywords = "APX-complete, Approximation ratio, Domination problems, NP-complete, Restrained domination",

author = "Lei Chen and Weiming Zeng and Changhong Lu",

year = "2012",

month = aug,

day = "24",

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

language = "英语",

volume = "448",

pages = "1--8",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - NP-completeness and APX-completeness of restrained domination in graphs

AU - Chen, Lei

AU - Zeng, Weiming

AU - Lu, Changhong

PY - 2012/8/24

Y1 - 2012/8/24

N2 - Let G=(V,E) be a simple graph. A vertex set S⊆V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V-S. In this paper, we investigate the NP-completeness of the restrained domination problem in planar graphs and split graphs. Meanwhile, it is proved that the restrained domination problem is APX-complete for bounded-degree graphs.

AB - Let G=(V,E) be a simple graph. A vertex set S⊆V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V-S. In this paper, we investigate the NP-completeness of the restrained domination problem in planar graphs and split graphs. Meanwhile, it is proved that the restrained domination problem is APX-complete for bounded-degree graphs.

KW - APX-complete

KW - Approximation ratio

KW - Domination problems

KW - NP-complete

KW - Restrained domination

UR - https://www.scopus.com/pages/publications/84863316910

U2 - 10.1016/j.tcs.2012.05.005

DO - 10.1016/j.tcs.2012.05.005

M3 - 文章

AN - SCOPUS:84863316910

SN - 0304-3975

VL - 448

SP - 1

EP - 8

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

NP-completeness and APX-completeness of restrained domination in graphs

摘要

访问文件

其它文件与链接

指纹

引用此