An Algorithmic Analysis of the Honey-Bee Game

Details An Algorithmic Analysis of the Honey-Bee Game An Algorithmic Analysis of the Honey-Bee Game

2011-02-15

arxiv.org/abs/1102.3025v1

Computer Science

Computer Science and Game Theory

20 pages, 9 figures

Scientific paper

The Honey-Bee game is a two-player board game that is played on a connected hexagonal colored grid or (in a generalized setting) on a connected graph with colored nodes. In a single move, a player calls a color and thereby conquers all the nodes of that color that are adjacent to his own current territory. Both players want to conquer the majority of the nodes. We show that winning the game is PSPACE-hard in general, NP-hard on series-parallel graphs, but easy on outerplanar graphs. In the solitaire version, the goal of the single player is to conquer the entire graph with the minimum number of moves. The solitaire version is NP-hard on trees and split graphs, but can be solved in polynomial time on co-comparability graphs.

Affiliated with

Also associated with

No associations

Rating

An Algorithmic Analysis of the Honey-Bee Game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Algorithmic Analysis of the Honey-Bee Game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algorithmic Analysis of the Honey-Bee Game will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-378228