arXiv Open Access 2019

An FPT algorithm for orthogonal buttons and scissors

Dekel Tsur

Lihat Sumber

Abstrak

We study the puzzle game Buttons and Scissors in which the goal is to remove all buttons from an $n\times m$ 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 \log k)} (n+m)^{O(1)}$, where $k$ is an upper bound on the number of cuts.

Topik & Kata Kunci

cs.DS

Penulis (1)

Dekel Tsur

Format Sitasi

APA MLA BibTeX

Tsur, D. (2019). An FPT algorithm for orthogonal buttons and scissors. https://arxiv.org/abs/1907.10230

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2019
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓