Complexity and approximation ratio of semitotal domination in graphs

DOI10.22049/cco.2018.25987.1065zbMath1394.05093OpenAlexW2912884031MaRDI QIDQ4583541

Pu Wu, Zehui Shao

Publication date: 31 August 2018

Full work available at URL: http://comb-opt.azaruniv.ac.ir/article_13748_70d5d03f125812cbc3dc8d0aec38312f.pdf

zbMATH Keywords

NP-completenessAPX-completesemitotal domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ The semitotal domination problem in block graphs

Cites Work

• NP-completeness and APX-completeness of restrained domination in graphs
• Optimization, approximation, and complexity classes
• Semitotal domination in claw-free cubic graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity and approximation ratio of semitotal domination in graphs