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

DOI10.1016/J.TCS.2007.05.027MaRDI QIDQ2456358zbMATH OpenOpenAlexFDO

Authors Hajo Broersma, Xueliang 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

all-ones problembipartite graphcomputational complexityodd dominating setplanar graph

Mathematics Subject Classification ID

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

Recommendations

• The Minimum All-Ones Problem for Trees
• Dominating sets for split and bipartite graphs
• The Minimum All-Ones Problem for Graphs with Small Treewidth
• Three new versions of the all-ones problem
• Finding a dominating set on bipartite graphs

Cites work

• \(\sigma\)-Automata and Chebyshev-polynomials
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata
• Characterizing switch-setting problems^∗
• Connected odd dominating sets in graphs
• Fibonacci polynomials and parity domination in grid graphs
• Graph theory
• scientific article; zbMATH DE number 436064 (Why is no real title available?)
• scientific article; zbMATH DE number 4074498 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161323 (Why is no real title available?)
• scientific article; zbMATH DE number 1934394 (Why is no real title available?)
• scientific article; zbMATH DE number 871170 (Why is no real title available?)
• scientific article; zbMATH DE number 894703 (Why is no real title available?)
• scientific article; zbMATH DE number 1420902 (Why is no real title available?)
• Linear cellular automata and the garden-of-eden
• Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs
• Note on the lamp lighting problem
• Odd and residue domination numbers of a graph
• Parity dimension for graphs
• The Minimum All-Ones Problem for Trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The σ-Game and Cellular Automata

Cited in

(10)

• Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
• A note on the complexity of minimum dominating set
• Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs
• The Minimum All-Ones Problem for Graphs with Small Treewidth
• The Minimum All-Ones Problem for Trees
• Complexity of unique (optimal) solutions in graphs: vertex cover and domination
• Three new versions of the all-ones problem
• A parameterized perspective of \textsc{all-colors}
• A parameterized perspective of \textsc{All-Colors}
• The general \(\sigma \) all-ones problem for trees

This page was built for publication: On the complexity of dominating set problems related to the minimum all-ones problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2456358)