Back to Search
Start Over
Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- Source :
-
Theoretical Computer Science . Nov2009, Vol. 410 Issue 47-49, p5063-5071. 9p. - Publication Year :
- 2009
-
Abstract
- Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 410
- Issue :
- 47-49
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 44584567
- Full Text :
- https://doi.org/10.1016/j.tcs.2009.08.004