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

DOI10.1016/j.tcs.2009.08.004zbMath1194.68260OpenAlexW2036622168WikidataQ60630618 ScholiaQ60630618MaRDI QIDQ1034626

Lei Chen, Zhenbing Zeng, Chang-hong Lu

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.004

zbMATH Keywords

combinatorial problemsapproximation algorithmspaired-dominationdomination problems\(APX\)-complete

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (13)

A linear-time algorithm for weighted paired-domination on block graphs ⋮ Vertices in all minimum paired-dominating sets of block graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms] ⋮ Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs ⋮ NP-completeness and APX-completeness of restrained domination in graphs ⋮ Complexity of distance paired-domination problem in graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Paired Domination in Graphs ⋮ A linear-time algorithm for paired-domination on circular-arc graphs

Cites Work

• Paired-domination in inflated graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Paired-domination of trees
• Paired domination on interval and circular-arc graphs
• A threshold of ln n for approximating set cover
• Paired-domination in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hardness results and approximation algorithms for (weighted) paired-domination in graphs