The general \(\sigma \) all-ones problem for trees

DOI10.1016/j.dam.2007.08.042zbMath1152.05317OpenAlexW2011832429MaRDI QIDQ944730

Chao Wang, Xiaoyan Zhang, Xue Liang Li

Publication date: 10 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.08.042

zbMATH Keywords

treealgorithmlinear timegeneral \(\sigma \) all-ones problemminimum \(\sigma \) all-ones problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata
• The constructibility of a configuration in a cellular automaton
• Linear cellular automata and the garden-of-eden
• On the computational complexity of finite cellular automata
• \(\sigma\)-Automata and Chebyshev-polynomials
• The Minimum All-Ones Problem for Trees
• The σ-Game and Cellular Automata
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Note on the lamp lighting problem