On the complexity of dominating set problems related to the minimum all-ones problem

DOI10.1016/j.tcs.2007.05.027zbMath1124.68076OpenAlexW2049357728MaRDI QIDQ2456358

Hajo J. Broersma, Xue Liang Li

Publication date: 18 October 2007

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

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

zbMATH Keywords

computational complexitybipartite graphplanar graphall-ones problemodd dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?

Cites Work

• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata
• Parity dimension for graphs
• Fibonacci polynomials and parity domination in grid graphs
• Linear cellular automata and the garden-of-eden
• \(\sigma\)-Automata and Chebyshev-polynomials
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Odd and residue domination numbers of a graph
• Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs
• Characterizing switch-setting problems^∗
• The Minimum All-Ones Problem for Trees
• The σ-Game and Cellular Automata
• Connected odd dominating sets in graphs
• Note on the lamp lighting problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item