2 citations · 3 across the 6 of their papers we have counts for
4 papers · 1 filter
Sorting Balls and Water: Equivalence and Computational Complexity
Takehiro Ito, Jun Kawahara, Shin-ichi Minato +7
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled…
Computational Complexity of Jumping Block Puzzles
Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara
In combinatorial reconfiguration, the reconfiguration problems on a vertex subset (e.g., an independent set) are well investigated. In these problems, some tokens are placed on a s…
Cyclic Shift Problems on Graphs
Kwon Kham Sai, Ryuhei Uehara, Giovanni Viglietta
We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished c…
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…