Davide Bilò

collaborators

3 papers

cs.DS2026

Fault-Tolerant ST-Diameter Oracles

Davide BilÃ², Keerti Choudhary, Sarel Cohen +3

Given two vertex sets $S$ and $T$ in a graph, the $S T$ -diameter is the maximum $s$ - $t$ -distance between vertices $s \in S$ and $t \in T$ . We study the problem of estimating the $ST…

cs.CC2026

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…

cs.DS2025

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 $G$ , we say that an edge is monitored by a pair…