Complexity and approximation ratio of semitotal domination in graphs

DOI10.22049/CCO.2018.25987.1065zbMATH Open1394.05093OpenAlexW2912884031MaRDI QIDQ4583541FDOQ4583541

Authors: Zehui Shao, Pu Wu 

Publication date: 31 August 2018

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

Recommendations

• Algorithmic aspects of semitotal domination in graphs
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• A linear-time algorithm for semitotal domination in strongly chordal graphs
• The semitotal domination problem in block graphs
• Semitotal domination subdivision numbers of graphs

zbMATH Keywords

NP-completenessAPX-completesemitotal domination

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization, approximation, and complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• NP-completeness and APX-completeness of restrained domination in graphs
• Semitotal domination in claw-free cubic graphs
• Semitotal domination in graphs

Cited In (5)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4583541)