research
∙
05/18/2023
On the Computational Complexity of Generalized Common Shape Puzzles
In this study, we investigate the computational complexity of some varia...
share
research
∙
12/23/2022
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains
Planar/flat configurations of fixed-angle chains and trees are well stud...
research
∙
02/19/2022
Sorting Balls and Water: Equivalence and Computational Complexity
Various forms of sorting problems have been studied over the years. Rece...
research
∙
10/07/2021
Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions
A rep-tile is a polygon that can be dissected into smaller copies (of th...
research
∙
09/09/2021
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings
We show that several classes of polyhedra are joined by a sequence of O(...
research
∙
09/06/2021
Computational Complexity of Jumping Block Puzzles
In combinatorial reconfiguration, the reconfiguration problems on a vert...
research
∙
05/29/2021
Efficient Folding Algorithms for Regular Polyhedra
We investigate the folding problem that asks if a polygon P can be folde...
research
∙
12/21/2020
Efficient Segment Folding is Hard
We introduce a computational origami problem which we call the segment f...
research
∙
09/23/2020
Cyclic Shift Problems on Graphs
We study a new reconfiguration problem inspired by classic mechanical pu...
research
∙
05/16/2020
Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots
A swarm of anonymous oblivious mobile robots, operating in deterministic...
research
∙
05/01/2019
Reconfiguring Undirected Paths
We consider problems in which a simple path of fixed length, in an undir...
research
∙
06/21/2018
Shortest Reconfiguration Sequence for Sliding Tokens on Spiders
Suppose that two independent sets I and J of a graph with I = J are ...
research
∙
03/19/2018