NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs

DOI10.33048/daio.2020.27.657zbMath1491.68080OpenAlexW4244661030MaRDI QIDQ5090153

Yury L. Orlovich, Yaroslav Anatol'Evich Loverov

Publication date: 15 July 2022

Published in: Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/da951

zbMATH Keywords

bipartite graphNP-completenesscubic graphplanar graphindependent dominating set

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Connected dominating set. Theory and applications
• Independent dominating set problem revisited
• The neighbourhood number of a graph
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Independent domination in graphs: A survey and recent results
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Total domination in graphs
• Total Domination in Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs