5 papers
On the complexity of the single-move labeled token routing problem
Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad +1
In neutral-atom quantum computers, atoms are moved to target positions along paths of empty positions, and a target position may be reserved for one species of atom. Motivated by t…
On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers
Nicolas Bousquet, Amer E. Mouawad, Stephanie Maaz +2
Solution discovery asks whether a given (infeasible) starting configuration to a problem can be transformed into a feasible solution using a limited number of transformation steps.…
On the complexity of constrained reconfiguration and motion planning
Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad +1
Coordinating the motion of multiple agents in constrained environments is a fundamental challenge in robotics, motion planning, and scheduling. A motivating example involves ro…
Efficient algorithms to solve atom reconfiguration problems. III. The bird and batching algorithms and other parallel implementations on GPUs
Fouad Afiouni, Remy El Sabeh, Naomi Nishimura +3
We present efficient implementations of atom reconfiguration algorithms for both CPUs and GPUs, along with a batching routine to merge displacement operations for parallel executio…
Kernelization Complexity of Solution Discovery Problems
Mario Grobler, Stephanie Maaz, Amer E. Mouawad +3
In the solution discovery variant of a vertex (edge) subset problem on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph tog…