An algorithmic analysis of the honey-bee game

R. Fleischer, G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)

Samenvatting

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 nodes of that color that are adjacent to his own 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. The solitaire version, where the goal is to conquer the entire graph with a minimum number of moves, is NP-hard on trees and split graphs, but can be solved in polynomial time on co-comparability graphs.
Originele taal-2Engels
TitelFun with Algorithms (5th International Conference, FUN 2010, Iscia, Italy, June 2-4, 2010. Proceedings)
RedacteurenP. Boldi
Plaats van productieBerlin
UitgeverijSpringer
Pagina's178-189
ISBN van geprinte versie978-3-642-13121-9
DOI's
StatusGepubliceerd - 2010

Publicatie series

NaamLecture Notes in Computer Science
Volume6099
ISSN van geprinte versie0302-9743

Vingerafdruk

Duik in de onderzoeksthema's van 'An algorithmic analysis of the honey-bee game'. Samen vormen ze een unieke vingerafdruk.

Citeer dit