Independent dominating set problem revisited

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

Sheung-Hung Poon, Ching-Hao Liu, 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 set; NP-complete; independent dominating set; \((k,\ell)\)-graph; at-most-cubic grid graph; cubic bipartite graph; FPT-algorithm; weighted independent dominating set

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms