On approximating the minimum independent dominating set
From MaRDI portal
Publication:750159
DOI10.1016/0020-0190(91)90188-NzbMath0713.68033WikidataQ126981891 ScholiaQ126981891MaRDI QIDQ750159
Publication date: 1991
Published in: Information Processing Letters (Search for Journal in Brave)
computational complexitycombinatorial problemspolynomial-time approximation algorithmNP-hard graph problems
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Independent domination in directed graphs ⋮ 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 ⋮ Balanced independent and dominating sets on colored interval graphs ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Iterative construction of the minimum independent dominating sets in hypercube graphs ⋮ Multi-constructor CMSA for the maximum disjoint dominating sets problem ⋮ \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms] ⋮ Bounds on 2-point set domination number of a graph ⋮ Sparsification and subexponential approximation ⋮ The bottleneck independent domination on the classes of bipartite graphs and block graphs. ⋮ Independent dominating set problem revisited ⋮ Polynomially bounded minimization problems which are hard to approximate ⋮ Approximating the minimum maximal independence number ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ Small \(k\)-pyramids and the complexity of determining \(k\) ⋮ A tight bound on the number of mobile servers to guarantee transferability among dominating configurations ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ The complexity of dissociation set problems in graphs ⋮ An analysis of root functions -- a subclass of the impossible class of faulty functions (ICFF) ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ On the complexity of independent dominating set with obligations in graphs ⋮ The b-chromatic number of a graph ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm ⋮ Nearly perfect sets in graphs ⋮ On approximability of the independent/connected edge dominating set problems
Cites Work
This page was built for publication: On approximating the minimum independent dominating set
