NP-completeness and APX-completeness of restrained domination in graphs
DOI10.1016/J.TCS.2012.05.005zbMATH Open1243.68184OpenAlexW2039024583WikidataQ60630583 ScholiaQ60630583MaRDI QIDQ442103FDOQ442103
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
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
- 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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Title not available (Why is that?)
- Graphs with large restrained domination number
- Restrained domination in graphs
- Restrained domination in trees
- Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs
- Remarks on restrained domination and total restrained domination in graphs
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Title not available (Why is that?)
- Total restrained domination numbers of trees
- On total restrained domination in graphs
- 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
- Total restrained domination in trees
- Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- Total restrained domination in cubic graphs
- A note on restrained domination in trees.
- Restrained domination in cubic graphs
- Restrained domination in claw-free graphs with minimum degree at least two
Cited In (8)
- Title not available (Why is that?)
- Complexity and approximation ratio of semitotal domination in graphs
- A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
- Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials
- Algorithmic and complexity aspects of problems related to total restrained domination for graphs
- Total (restrained) domination in unit disk graphs
- Restrained domination in some subclasses of chordal 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)
