Davide Bilò

collaborators

5 papers

cs.DS2026

Near-Optimal Replacement Path Coverings

Davide Bilò, Keerti Choudhary, Sarel Cohen +1

Let $L$ and $f$ be positive integers. An $(L, f)$ -replacement path covering (RPC) for a graph $G$ is a family $G$ of subgraphs such that, for every set $F$ of at most $f$ …

cs.DS2026

Simpler and Improved Replacement Path Coverings

Davide Bilò, Shiri Chechik, Keerti Choudhary +2

An important tool in the design of fault-tolerant graph data structures are $(L, f)$ -replacement path coverings (RPCs). An RPC is a family $G$ of subgraphs of a given grap…

cs.DS2024

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks

Davide Bilò, Keerti Choudhary, Sarel Cohen +2

We design sensitivity oracles for error-prone networks. For a network problem $Π$ , the data structure preprocesses a network $G = (V, E)$ and sensitivity parameter $f$ such that, for…

cs.GT2024

Temporal Network Creation Games: The Impact of Non-Locality and Terminals

Davide Bilò, Sarel Cohen, Tobias Friedrich +4

We live in a world full of networks where our economy, our communication, and even our social life crucially depends on them. These networks typically emerge from the interaction o…

cs.DS2024

Improved Distance (Sensitivity) Oracles with Subquadratic Space

Davide Bilò, Shiri Chechik, Keerti Choudhary +3

A distance oracle (DO) with stretch $(α, β)$ for a graph $G$ is a data structure that, when queried with vertices $s$ and $t$ , returns a value $d (s, t)$ such that $d(s,t)…