A Survey on the Complexity of Flood-Filling Games

DOI10.1007/978-3-319-98355-4_20MaRDI QIDQ6163636zbMATH OpenOpenAlexFDO

Authors Michael R. Fellows, Frances Rosamond, Maise Dantas da Silva, Uéverton S. Souza

Publication date 30 June 2023

Published in Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-98355-4_20

zbMATH Keywords

combinatorial gamesflood-filling gamesflood-itfree-flood-itgraph algorithmsparameterized complexity

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parameterized complexity of flood-filling games on trees
• Tractability and hardness of flood-filling games on trees
• The complexity of flood-filling games on graphs
• The complexity of flood filling games
• Extremal properties of flood-filling games

Cites work

• Algorithmic meta-theorems for restrictions of treewidth
• Algorithms and Data Structures
• Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
• An algorithmic analysis of the Honey-Bee game
• Analogs & duals of the MAST problem for sequences & trees
• Call routing and the ratcatcher
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Efficient algorithms for inferring evolutionary trees
• Flooding games on graphs
• scientific article; zbMATH DE number 6399334 (Why is no real title available?)
• More on the complexity of common superstring and supersequence problems
• On complexity of flooding games on graphs with interval representations
• On the complexity of DNA physical mapping
• Parameterized complexity of flood-filling games on trees
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Spanning trees and the complexity of flood-filling games
• The complexity of flood filling games
• The complexity of flood-filling games on graphs
• The complexity of free-flood-it on \(2\times n\) boards
• The consensus string problem for a metric is NP-complete
• The Flood-It game parameterized by the vertex cover number
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• The shortest common supersequence problem over binary alphabet is NP- complete
• Tractability and hardness of flood-filling games on trees
• Triangulating Vertex-Colored Graphs

Cited in

(8)

• Tractability and hardness of flood-filling games on trees
• Flooding games on graphs
• On complexity of flooding games on graphs with interval representations
• The complexity of free-flood-it on \(2\times n\) boards
• How Bad is the Freedom to Flood-It?
• Parameterized complexity of flood-filling games on trees
• Extremal properties of flood-filling games
• Vexing vexillological logic

This page was built for publication: A Survey on the Complexity of Flood-Filling Games

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