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

DOI10.1016/j.tcs.2012.05.005zbMath1243.68184OpenAlexW2039024583WikidataQ60630583 ScholiaQ60630583MaRDI QIDQ442103

Weiming Zeng, Lei Chen, Chang-hong Lu

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-completeAPX-completerestrained dominationapproximation ratiodomination 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)

Related Items (6)

Algorithmic and complexity aspects of problems related to total restrained domination for graphs ⋮ Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials ⋮ Restrained domination and its variants in extended supergrid graphs ⋮ Unnamed Item ⋮ Complexity and approximation ratio of semitotal domination in graphs ⋮ A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restrained domination in cubic graphs
• Total restrained domination in trees
• Total restrained domination in graphs with minimum degree two
• An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree
• Restrained domination in claw-free graphs with minimum degree at least two
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• Total restrained domination in cubic graphs
• Optimization, approximation, and complexity classes
• Graphs with large restrained domination number
• Restrained domination in graphs
• Some APX-completeness results for cubic graphs
• Restrained domination in trees
• Total restrained domination numbers of trees
• Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs
• A threshold of ln n for approximating set cover
• On total restrained domination in graphs
• Remarks on restrained domination and total restrained domination in graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Algorithms for Vertex Partitioning Problems on Partial k-Trees

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