NP-completeness and APX-completeness of restrained domination in graphs
NP-completeness and APX-completeness of restrained domination in graphs
复制标题
图中受限支配的 NP 完备性和 APX 完备性
DOI：
10.1016/j.tcs.2012.05.005
复制
发表时间：
2012-08
影响因子：
1.1
通讯作者：
Lu, Changhong
中科院分区：
文献类型：
--
作者：
Chen, Lei;Zeng, Weiming;Lu, Changhong
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.
登录
查看更多内容
DOI：
10.1007/b102533
发表时间：
2013
期刊：
Springer US
影响因子：
--
作者：
通讯作者：
--
DOI：
10.1016/j.dam.2009.03.010
发表时间：
2009-07
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
J. Hattingh;Ernst J. Joubert
通讯作者：
J. Hattingh;Ernst J. Joubert
DOI：
10.1007/978-1-4613-0303-9
发表时间：
1998-10
期刊：
--
影响因子：
--
作者：
D. Du;P. Pardalos
通讯作者：
D. Du;P. Pardalos
DOI：
10.1007/978-3-642-58412-1
发表时间：
1999
期刊：
--
影响因子：
--
作者：
G. Ausiello;A. Marchetti-Spaccamela;P. Crescenzi;G. Gambosi;M. Protasi;V. Kann
通讯作者：
G. Ausiello;A. Marchetti-Spaccamela;P. Crescenzi;G. Gambosi;M. Protasi;V. Kann
DOI：
10.1007/978-3-8348-9329-1_2
发表时间：
2010
期刊：
--
影响因子：
--
作者：
M. Loebl
通讯作者：
M. Loebl