On approximating the minimum independent dominating set

DOI10.1016/0020-0190(91)90188-NzbMATH Open0713.68033WikidataQ126981891 ScholiaQ126981891MaRDI QIDQ750159FDOQ750159

Authors: Robert W. Irving 

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycombinatorial problemspolynomial-time approximation algorithmNP-hard graph problems

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• P-Complete Approximation Problems
• The NP-completeness column: An ongoing guide
• Independent domination in chordal graphs
• The Complexity of Near-Optimal Graph Coloring
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (48)

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