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

DOI10.1016/j.dam.2007.08.042zbMath1152.05317MaRDI 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

tree; algorithm; linear time; general \(\sigma \) all-ones problem; minimum \(\sigma \) all-ones problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

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