A Survey on the Complexity of Flood-Filling Games
From MaRDI portal
Publication:6163636
DOI10.1007/978-3-319-98355-4_20zbMath1514.68214OpenAlexW2885024233MaRDI QIDQ6163636
Michael R. Fellows, Maise Dantas da Silva, Uéverton S. Souza, Frances A. Rosamond
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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- The Flood-It game parameterized by the vertex cover number
- The complexity of free-flood-it on \(2\times n\) boards
- The complexity of flood-filling games on graphs
- Spanning trees and the complexity of flood-filling games
- The complexity of flood filling games
- An algorithmic analysis of the Honey-Bee game
- The consensus string problem for a metric is NP-complete
- The shortest common supersequence problem over binary alphabet is NP- complete
- More on the complexity of common superstring and supersequence problems
- Call routing and the ratcatcher
- On the complexity of DNA physical mapping
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Algorithmic meta-theorems for restrictions of treewidth
- Tractability and hardness of flood-filling games on trees
- Flooding games on graphs
- On Complexity of Flooding Games on Graphs with Interval Representations
- Connected Coloring Completion for General Graphs: Algorithms and Complexity
- Triangulating Vertex-Colored Graphs
- Analogs & duals of the MAST problem for sequences & trees
- Parameterized Complexity of Flood-Filling Games on Trees
- Algorithms and Data Structures
- Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
- Efficient algorithms for inferring evolutionary trees
