Spanning trees and the complexity of flood-filling games

DOI10.1007/s00224-013-9482-zzbMath1303.05127arXiv1203.2538OpenAlexW2568998114MaRDI QIDQ489766

Kitty Meeks, Alexander D. Scott

Publication date: 21 January 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.2538

zbMATH Keywords

computational complexitygraph colouringgames on graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (7)

Unnamed Item ⋮ The Flood-It game parameterized by the vertex cover number ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ How Bad is the Freedom to Flood-It? ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Complexity and computation of connected zero forcing ⋮ Tractability and hardness of flood-filling games on trees

Cites Work

• Unnamed Item
• The complexity of free-flood-it on \(2\times n\) boards
• The complexity of flood-filling games on graphs
• The complexity of flood filling games
• An algorithmic analysis of the Honey-Bee game
• Flooding games on graphs
• On Complexity of Flooding Games on Graphs with Interval Representations

This page was built for publication: Spanning trees and the complexity of flood-filling games