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

^*Corresponding author for this work

School of Mathematical Sciences

East China Normal University

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

18 Scopus citations

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.

Original language	English
Pages (from-to)	5063-5071
Number of pages	9
Journal	Theoretical Computer Science
Volume	410
Issue number	47-49
DOIs	https://doi.org/10.1016/j.tcs.2009.08.004
State	Published - 6 Nov 2009

Keywords

APX-complete
Approximation algorithms
Combinatorial problems
Domination problems
Paired-domination

Access to Document

10.1016/j.tcs.2009.08.004

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this