An FPT algorithm for orthogonal buttons and scissors

DOI10.1016/J.IPL.2020.105997MaRDI QIDQ2203593zbMATH OpenOpenAlexFDO

Authors Dekel Tsur

Publication date 7 October 2020

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.10230

zbMATH Keywords

algorithmscombinatorial puzzlesparameterized complexityreduction rules

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40) Combinatorial games (91A46)

Abstract: We study the puzzle game Buttons and Scissors in which the goal is to remove all buttons from an $nimesm$ grid by a series of horizontal and vertical cuts. We show that the corresponding parameterized problem has an algorithm with time complexity $2^{O(k^{2}logk)}(n+m{)}^{O(1)}$, where $k$ is an upper bound on the number of cuts.

Recommendations

• Single-player and two-player buttons \& scissors games (extended abstract)
• scientific article; zbMATH DE number 1944412
• Snipperclips: cutting tools into desired polygons using themselves
• Crazy-cuts: from theory to app
• A polynomial algorithm for one problem of guillotine cutting

Cites work

• Single-player and two-player buttons \& scissors games (extended abstract)

Cited in

(2)

• Snipperclips: cutting tools into desired polygons using themselves
• Single-player and two-player buttons \& scissors games (extended abstract)

This page was built for publication: An FPT algorithm for orthogonal buttons and scissors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2203593)