Linear time algorithms for Clobber
<|reference_start|>Linear time algorithms for Clobber: We 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.<|reference_end|>
@article{blondel2007linear,
    title={Linear time algorithms for Clobber},
    author={Vincent D. Blondel, Julien M. Hendrickx and Raphael M. Jungers},
    journal={arXiv preprint arXiv:cs/0703054},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0703054},
    primaryClass={cs.GT}
}