Hardness results and approximation algorithms for (weighted) paired-domination in graphs

Lei Chen; Changhong Lu; Zhenbing Zeng

doi:10.1016/j.tcs.2009.08.004

Hardness results and approximation algorithms for (weighted) paired-domination in graphs

Lei Chen
, Changhong Lu^*
, Zhenbing Zeng

^*此作品的通讯作者

数学科学学院

East China Normal University

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

20 引用（Scopus）

摘要

Let G = (V, E) be a simple graph without isolated vertices. A vertex set S ⊆ V is a paired- dominating set if every vertex in V - S has a neighbor in S and the induced subgraph GTSU has a perfect matching. In this paper, we investigate the approximation hardness of paired- domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given.

源语言	英语
页（从-至）	5063-5071
页数	9
期刊	Theoretical Computer Science
卷	410
期	47-49
DOI	https://doi.org/10.1016/j.tcs.2009.08.004
出版状态	已出版 - 6 11月 2009

访问文件

10.1016/j.tcs.2009.08.004

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{5f572b7b907e4908ad40a62a59c91737,

title = "Hardness results and approximation algorithms for (weighted) paired-domination in graphs",

abstract = "Let G = (V, E) be a simple graph without isolated vertices. A vertex set S ⊆ V is a paired- dominating set if every vertex in V - S has a neighbor in S and the induced subgraph GTSU has a perfect matching. In this paper, we investigate the approximation hardness of paired- domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given.",

keywords = "APX-complete, Approximation algorithms, Combinatorial problems, Domination problems, Paired-domination",

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

year = "2009",

month = nov,

day = "6",

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

language = "英语",

volume = "410",

pages = "5063--5071",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "47-49",

}

TY - JOUR

T1 - Hardness results and approximation algorithms for (weighted) paired-domination in graphs

AU - Chen, Lei

AU - Lu, Changhong

AU - Zeng, Zhenbing

PY - 2009/11/6

Y1 - 2009/11/6

N2 - Let G = (V, E) be a simple graph without isolated vertices. A vertex set S ⊆ V is a paired- dominating set if every vertex in V - S has a neighbor in S and the induced subgraph GTSU has a perfect matching. In this paper, we investigate the approximation hardness of paired- domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given.

AB - Let G = (V, E) be a simple graph without isolated vertices. A vertex set S ⊆ V is a paired- dominating set if every vertex in V - S has a neighbor in S and the induced subgraph GTSU has a perfect matching. In this paper, we investigate the approximation hardness of paired- domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given.

KW - APX-complete

KW - Approximation algorithms

KW - Combinatorial problems

KW - Domination problems

KW - Paired-domination

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

U2 - 10.1016/j.tcs.2009.08.004

DO - 10.1016/j.tcs.2009.08.004

M3 - 文章

AN - SCOPUS:79952340971

SN - 0304-3975

VL - 410

SP - 5063

EP - 5071

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 47-49

ER -

Hardness results and approximation algorithms for (weighted) paired-domination in graphs

摘要

访问文件

其它文件与链接

指纹

引用此