Tractability and hardness of flood-filling games on trees

DOI10.1016/j.tcs.2015.02.008zbMath1312.68090OpenAlexW1991549273MaRDI QIDQ2344738

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

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

NP-hardnessfixed-parameter tractabilityFlood-ItW[1-hardness]shortest common supersequenceflood-filling games on treesFree-Flood-Itphylogenetic colored trees

Mathematics Subject Classification ID

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

Related Items (5)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On the complexity of DNA physical mapping
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Flooding games on graphs
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• The Complexity of Some Problems on Subsequences and Supersequences
• 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

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