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

\((k,\ell)\)-graphat-most-cubic grid graphcubic bipartite graphdominating setFPT-algorithmindependent dominating setNP-completeweighted independent dominating set

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(14)

• The bottleneck independent domination on the classes of bipartite graphs and block graphs.
• The weighted independent domination problem is NP-complete for chordal graphs
• On the complexity of independent dominating set with obligations in graphs
• On the independent dominating set polytope
• Finding a maximum minimal separator: graph classes and fixed-parameter tractability
• Complexity of the approximation of the independent dominating set problem in the class of 2P₃-free perfect graphs
• Algorithmic results of independent k-domination on weighted graphs
• scientific article; zbMATH DE number 1367677 (Why is no real title available?)
• Algorithmic aspects of some variants of domination in graphs
• NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• Independent strong weak domination: A mathematical programming approach
• On the kernel and related problems in interval digraphs
• The domination and independent domination numbers of some families of snarks

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)