An algorithmic analysis of the Honey-Bee game

DOI10.1016/j.tcs.2012.05.032zbMath1247.68097OpenAlexW2064727996MaRDI QIDQ714789

Rudolf Fleischer, Gerhard J. Woeginger

Publication date: 11 October 2012

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

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

zbMATH Keywords

computational complexitycombinatorial gamegraph problem

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Related Items (11)

Unnamed Item ⋮ The Flood-It game parameterized by the vertex cover number ⋮ The complexity of free-flood-it on \(2\times n\) boards ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ The complexity of flood-filling games on graphs ⋮ How Bad is the Freedom to Flood-It? ⋮ Flooding games on graphs ⋮ Spanning trees and the complexity of flood-filling games ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ The unit-capacity constrained permutation problem ⋮ Tractability and hardness of flood-filling games on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• Computing a perfect strategy for nxn chess requires time exponential in n
• Comparability graphs and intersection graphs
• Gobang is PSPACE-complete
• The Othello game on an \(n\times n\) board is PSPACE-complete
• More on the complexity of common superstring and supersequence problems
• N by N Checkers is Exptime Complete
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• GO Is Polynomial-Space Hard
• TETRIS IS HARD, EVEN TO APPROXIMATE
• Mathematical Foundations of Computer Science 2003

This page was built for publication: An algorithmic analysis of the Honey-Bee game