2 citations · 3 across the 5 of their papers we have counts for
10 papers
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…
Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions
Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama +7
A rep-tile is a polygon that can be dissected into smaller copies (of the same size) of the original polygon. A polyomino is a polygon that is formed by joining one or more unit sq…
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…
Efficient Folding Algorithms for Regular Polyhedra
Tonan Kamata, Akira Kadoguchi, Takashi Horiyama +1
We investigate the folding problem that asks if a polygon P can be folded to a polyhedron Q for given P and Q. Recently, an efficient algorithm for this problem has been developed…
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…
Reconfiguring Undirected Paths
Erik D. Demaine, David Eppstein, Adam Hesterberg +4
We consider problems in which a simple path of fixed length, in an undirected graph, is to be shifted from a start position to a goal position by moves that add an edge to either e…