Tractability and hardness of flood-filling games on trees

DOI10.1016/J.TCS.2015.02.008MaRDI QIDQ2344738zbMATH OpenOpenAlexFDO

Authors Michael R. Fellows, Uéverton dos Santos Souza, Fábio Protti, Maise Dantas da Silva

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.02.008

zbMATH Keywords

fixed-parameter tractabilityflood-filling games on treesFlood-ItFree-Flood-ItNP-hardnessphylogenetic colored treesshortest common supersequenceW[1-hardness]

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problems related to evolution (92D15)

Recommendations

• Parameterized complexity of flood-filling games on trees
• A Survey on the Complexity of Flood-Filling Games
• The complexity of flood-filling games on graphs
• Spanning trees and the complexity of flood-filling games
• The complexity of flood filling games

Cites work

• Algorithms and Data Structures
• An algorithmic analysis of the Honey-Bee game
• Analogs & duals of the MAST problem for sequences & trees
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Efficient algorithms for inferring evolutionary trees
• Flooding games on graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• scientific article; zbMATH DE number 6399334 (Why is no real title available?)
• More on the complexity of common superstring and supersequence problems
• On the complexity of DNA physical mapping
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• 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 Complexity of Some Problems on Subsequences and Supersequences
• The consensus string problem for a metric is NP-complete
• 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
• Triangulating Vertex-Colored Graphs

Cited in

(8)

• Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
• The Flood-It game parameterized by the vertex cover number
• How bad is the freedom to Flood-It?
• The complexity of free-flood-it on \(2\times n\) boards
• How Bad is the Freedom to Flood-It?
• Spanning trees and the complexity of flood-filling games
• Parameterized complexity of flood-filling games on trees
• A Survey on the Complexity of Flood-Filling Games

This page was built for publication: Tractability and hardness of flood-filling games on trees

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