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

School of Mathematical Sciences

Shanghai Maritime University

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

9 Scopus citations

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.

Original language	English
Pages (from-to)	1-8
Number of pages	8
Journal	Theoretical Computer Science
Volume	448
DOIs	https://doi.org/10.1016/j.tcs.2012.05.005
State	Published - 24 Aug 2012

Keywords

APX-complete
Approximation ratio
Domination problems
NP-complete
Restrained domination

Access to Document

10.1016/j.tcs.2012.05.005

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this