Independent dominating set problem revisited

DOI10.1016/j.tcs.2014.09.001zbMath1303.68073OpenAlexW1985099784WikidataQ62041723 ScholiaQ62041723MaRDI QIDQ476836

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

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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (3)

Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs ⋮ On the kernel and related problems in interval digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the minimum independent dominating set
• Dominating sets for split and bipartite graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Clustering and domination in perfect graphs
• Independent domination in chordal graphs
• Unit disk graphs
• Optimization, approximation, and complexity classes
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• The weighted independent domination problem is NP-complete for chordal graphs
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Independent Domination on Tree Convex Bipartite Graphs
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
• Polynomial-time data reduction for dominating set
• The Problem of Compatible Representatives
• Approximation algorithms for NP-complete problems on planar graphs
• On the hardness of approximating minimization problems
• An induced subgraph characterization of domination perfect graphs
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE

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