The Minimum All-Ones Problem for Trees

DOI10.1137/S0097539703421620zbMath1056.05133MaRDI QIDQ4651469

Chao Wang, William Y. C. Chen, Xiaoyan Zhang, Xue Liang Li

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

graph algorithmtime complexityall-ones problemlamp lighting problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

On the complexity of dominating set problems related to the minimum all-ones problem ⋮ The general \(\sigma \) all-ones problem for trees ⋮ Minimum light number of lit-only \(\sigma\)-game on a tree ⋮ Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game? ⋮ A Survey of the Game “Lights Out!” ⋮ Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs

This page was built for publication: The Minimum All-Ones Problem for Trees