Posted on

Paper accepted to SODA 2020

The group just had a paper accepted to appear at the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA) in 2020. The title is “Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External Forces” and the authors are Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Mauricio Flores, Timothy Gomez, Austin Luchsinger, Rene Reyes, Robert Schweller, and Tim Wylie.

Posted on

Summer Xtreme Seminar

Come join us at the first Summer Xtreme Algorithms seminar! This is a quick set of 5 talks to showcase some of the work being done in the lab. These are 10 minute talks! If you’re interested in research, come see what topics might interest you. The talks are in IEAB 2.208 on 7/25 starting at 1 pm. For a full list of talks, see the flyer.

Posted on

Short abstract accepted at JCDCGGG

The short paper “Relocation with Uniform External Control in Limited Directions” was accepted at the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3). The paper will be presented at the conference in September in Tokyo. http://www.jcdcgg.u-tokai.ac.jp/

The authors on the paper are Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.

Posted on

Relocation with Uniform External Control in Limited Directions

Title: Relocation with Uniform External Control in Limited Directions (Short Abstract)
Authors: Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.
Conference: The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3’19), 2019.

Abstract: We study a model where particles exist within a board and move single units based on uniform external forces. We investigate the complexity of deciding whether a single particle can be relocated to another position in the board, and whether a board configuration can be transformed into another configuration. We prove that the problems are NP-Complete with $1 \times 1$ particles even when only allowed to move in 2 or 3 directions.