Independent dominating set problem revisited

DOI10.1016/J.TCS.2014.09.001MaRDI QIDQ476836zbMATH OpenOpenAlexWikidataFDO

Authors Ching-Hao Liu, Sheung-Hung Poon, Jin-Yong Lin

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.09.001

zbMATH Keywords

dominating setNP-completeindependent dominating set\((k,\ell)\)-graphat-most-cubic grid graphcubic bipartite graphFPT-algorithmweighted independent dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
• Algorithmic aspects of some variants of domination in graphs
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• On approximating the minimum independent dominating set
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• An induced subgraph characterization of domination perfect graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Clustering and domination in perfect graphs
• Dominating sets for split and bipartite graphs
• Independent domination in chordal graphs
• Independent domination on tree convex bipartite graphs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• On approximating the minimum independent dominating set
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• On the hardness of approximating minimization problems
• Optimal binary space partitions for segments in the plane
• Optimization, approximation, and complexity classes
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Polynomial-time data reduction for dominating set
• The Problem of Compatible Representatives
• The weighted independent domination problem is NP-complete for chordal graphs
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Unit disk graphs

Cited in

(11)

• The bottleneck independent domination on the classes of bipartite graphs and block graphs.
• Algorithmic results of independent \(k\)-domination on weighted graphs
• Independent strong weak domination: A mathematical programming approach
• The weighted independent domination problem is NP-complete for chordal graphs
• NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
• On the independent dominating set polytope
• On the kernel and related problems in interval digraphs
• Finding a maximum minimal separator: graph classes and fixed-parameter tractability
• Algorithmic aspects of some variants of domination in graphs
• Complexity of the approximation of the independent dominating set problem in the class of \(2P_3\)-free perfect graphs
• A branch-and-reduce algorithm for finding a minimum independent dominating set

This page was built for publication: Independent dominating set problem revisited

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