The complexity of free flood filling games (コンピュテーション)

スポンサーリンク

概要

• 論文の詳細を見る

• The flood filling games on a graph is a kind of graph coloring game. The one player version of the game is known as Flood-It, and the two player version is known as Honey-Bee Game. We consider the case that the player can color arbitrary vertex. This version is called free flood filling game. We concentrate at the one player version of the free flood filling game on a graph. In this paper, we show that the free Flood-It is NP-complete on trees with only three colors, and it is polynomial time solvable on paths and cycles with any number of colors.

• 2011-08-30

著者

• Uehara Ryuhei

  Japan Advanced Inst. Sci. And Technol. Nomi‐shi Jpn

• Uehara Ryuhei

  Japan Advanced Institute Of Science And Technology

• Uno Takeaki

  National Inst. Of Informatics

• Fukui Hiroyuki

  Japan Advanced Institute Of Science And Technology

• Nakanishi Akihiro

  Japan Advanced Institute of Science and Technology

• Uno Yushi

  Osaka Prefecture University

関連論文

• A short note on the reducibility of the collapsing knapsack problem
• Random Generation and Enumeration of Proper Interval Graphs
• Practical Techniques for Speeding Up Enumeration Algorithms for Frequent Itemset Mining Problems
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• AN O(n^2 log^2 n) ALGORITHM FOR INPUT-OR-OUTPUT TEST IN DISJUNCTIVE SCHEDULING
• Generating Chordal Graphs Included in Given Graphs
• Longest Path Problems on Ptolemaic Graphs
• The complexity of free flood filling games (コンピュテーション)
• Voronoi Game on a Path
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)

スポンサーリンク