4 papers
An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
Matteo Caporrella, Stefano Leucci
We study the Torus Puzzle, a solitaire game in which the elements of an input matrix need to be rearranged into a target configuration via a sequence of unit rotations…
Complexity Thresholds for the Constrained Colored Token Swapping Problem
Davide Bilò, Stefano Leucci, Andrea Martinelli
Consider the following puzzle: a farmland consists of several fields, each occupied by either a farmer, a fox, a chicken, or a caterpillar. Creatures in neighboring fields can swap…
On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
Davide Bilò, Giordano Colli, Luca Forlizzi +1
We study the minimum \emph{Monitoring Edge Geodetic Set} (\megset) problem introduced in [Foucaud et al., CALDAM'23]: given a graph , we say that an edge is monitored by a pair…
An Optimal Sorting Algorithm for Persistent Random Comparison Faults
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We consider the problem of sorting elements subject to persistent random comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (…