On approximating the minimum independent dominating set

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

Approximating the minimum maximal independence number
scientific article; zbMATH DE number 140152
On the complexity of approximating the independent set problem
Complexity of the approximation of the independent dominating set problem in the class of \(2P_3\)-free perfect graphs
Algorithms – ESA 2004

Cites work

scientific article; zbMATH DE number 3648727 (Why is no real title available?)
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
scientific article; zbMATH DE number 3799403 (Why is no real title available?)
Independent domination in chordal graphs
P-Complete Approximation Problems
The Complexity of Near-Optimal Graph Coloring
The NP-completeness column: An ongoing guide

Cited in

(49)

On approximability of the independent/connected edge dominating set problems
Approximating the minimum maximal independence number
The bottleneck independent domination on the classes of bipartite graphs and block graphs.
The b-chromatic number of a graph
The complexity of dissociation set problems in graphs
Nearly perfect sets in graphs
Multi-constructor CMSA for the maximum disjoint dominating sets problem
Balanced independent and dominating sets on colored interval graphs
A tight bound on the number of mobile servers to guarantee transferability among dominating configurations
The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
On the algorithmic complexity of twelve covering and independence parameters of graphs
Independent domination in directed graphs
Approximation hardness of dominating set problems in bounded degree graphs
A resource assignment problem on graphs
Combinatorial bounds via measure and conquer
Bounds on 2-point set domination number of a graph
Fast algorithms for \textsc{min independent dominating set}
On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
Small \(k\)-pyramids and the complexity of determining \(k\)
Two algorithms for determining a minimum independent dominating set
Approximating the minimum independent dominating set in perturbed graphs
Approximating the minimum independent dominating set in perturbed graphs
Approximating minimum independent dominating sets in wireless networks
Fast algorithms for min independent dominating set
scientific article; zbMATH DE number 2080196 (Why is no real title available?)
\([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms
On the complexity of the minimum independent set partition problem
Construction of Halin graph with perfect k-ary tree and its independent domination number
On independent domination parameters of some special families of Halin graph
On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
On the complexity of independent dominating set with obligations in graphs
Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
Complexity of the max cut problem with the minimal domination constraint
On Dominating Sets and Independent Sets of Graphs
Polynomially bounded minimization problems which are hard to approximate
Algorithms – ESA 2004
Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
An analysis of root functions -- a subclass of the impossible class of faulty functions (ICFF)
On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
scientific article; zbMATH DE number 140152 (Why is no real title available?)
Iterative construction of the minimum independent dominating sets in hypercube graphs
On computing minimal independent support and its applications to sampling and counting
Complexity of the approximation of the independent dominating set problem in the class of \(2P_3\)-free perfect graphs
An Efficient Local Search for the Minimum Independent Dominating Set Problem
Sparsification and subexponential approximation
On the complexity of approximating the independent set problem (extended abstract)
Independent dominating set problem revisited
Approximation hardness of domination problems on generalized convex graphs
A note on the complexity of minimum dominating set

This page was built for publication: On approximating the minimum independent dominating set

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