Linear time algorithms for Clobber

Simple item page
dc.creatorBlondel, Vincent D.
dc.creatorHendrickx, Julien M.
dc.creatorJungers, Raphael M.
dc.date2007-03-12
dc.date.accessioned2026-07-07T07:51:18Z
dc.date.available2026-07-07T07:51:18Z
dc.descriptionWe prove that the single-player game clobber is solvable in linear time when played on a line or on a cycle. For this purpose, we show that this game is equivalent to an optimization problem on a set of words defined by seven classes of forbidden patterns. We also prove that, playing on the cycle, it is always possible to remove at least 2n/3 pawns, and we give a conformation for which it is not possible to do better, answering questions recently asked by Faria et al.
dc.identifierhttps://arxiv.org/abs/cs/0703054
dc.identifierhttp://arxiv.org/abs/cs/0703054
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/125466
dc.subjectComputer Science and Game Theory
dc.titleLinear time algorithms for Clobber
dc.typetext

Files

Collections

arXiv