18 citations · 76 across the 24 of their papers we have counts for
35 papers
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…
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…
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 (…
On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
Davide Bilò, Giordano Colli, Luca Forlizzi +1
The minimum \emph{Monitoring Edge-Geodetic Set} problem asks for a minimum vertex subset such that for every edge of the input graph , there exist a two vertices $u,v \i…
Temporal queries for dynamic temporal forests
Davide Bilò, Luciano Gualà, Stefano Leucci +2
In a temporal forest each edge has an associated set of time labels that specify the time instants in which the edges are available. A temporal path from vertex to vertex i…
Graph Spanners for Group Steiner Distances
Davide Bilò, Luciano Gualà, Stefano Leucci +1
A spanner is a sparse subgraph of a given graph which preserves distances, measured w.r.t.\ some distance metric, up to a multiplicative stretch factor. This paper addresses th…