5 papers · 1 filter
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…
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 (…
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…