Davide Bilò

collaborators

Showing cs.DSShow all

5 papers · 1 filter

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.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…

cs.DS2024

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 $u$ to vertex $v$ i…

cs.DS2024

Graph Spanners for Group Steiner Distances

Davide BilÃ², Luciano GualÃ, Stefano Leucci +1

A spanner is a sparse subgraph of a given graph $G$ which preserves distances, measured w.r.t.\ some distance metric, up to a multiplicative stretch factor. This paper addresses th…

cs.DS2024

Approximate Distance Sensitivity Oracles in Subquadratic Space

Davide BilÃ², Shiri Chechik, Keerti Choudhary +4

An $f$ -edge fault-tolerant distance sensitive oracle ( $f$ -DSO) with stretch $I ¨ \geq 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertic…