NP-completeness and APX-completeness of restrained domination in graphs

DOI10.1016/J.TCS.2012.05.005MaRDI QIDQ442103zbMATH OpenOpenAlexWikidataFDO

Authors Weiming Zeng, Changhong Lu, Lei Chen

Publication date 9 August 2012

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

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

zbMATH Keywords

NP-completerestrained dominationapproximation ratioAPX-completedomination problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Restrained and total restrained domination in graphs
• On restricted domination in graphs
• Results on total restrained domination in graphs
• Restrained domination in graphs
• scientific article; zbMATH DE number 5531997
• Total restrained domination in graphs
• Complexity aspects of restrained Roman domination in graphs
• Algorithmic and NP-completeness aspects of a total lict domination number of a graph
• Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs
• Bounds on the total restrained domination number of a graph

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302196 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• A note on restrained domination in trees.
• A threshold of ln n for approximating set cover
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree
• Graphs with large restrained domination number
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs
• On total restrained domination in graphs
• Optimization, approximation, and complexity classes
• Remarks on restrained domination and total restrained domination in graphs
• Restrained domination in claw-free graphs with minimum degree at least two
• Restrained domination in cubic graphs
• Restrained domination in graphs
• Restrained domination in trees
• Some APX-completeness results for cubic graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Total restrained domination in cubic graphs
• Total restrained domination in graphs with minimum degree two
• Total restrained domination in trees
• Total restrained domination numbers of trees

Cited in

(7)

• Algorithmic and complexity aspects of problems related to total restrained domination for graphs
• Complexity and approximation ratio of semitotal domination in graphs
• Restrained domination in some subclasses of chordal graphs
• scientific article; zbMATH DE number 7509363 (Why is no real title available?)
• Total (restrained) domination in unit disk graphs
• A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
• Restrained domination and its variants in extended supergrid graphs

This page was built for publication: NP-completeness and APX-completeness of restrained domination in graphs

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