Davide Bilò

activity

20112026

most citedLocality-based Network Creation Games

18 citations · 44 across the 26 of their papers we have counts for

collaborators

Showing 2021 · cs.DSShow all

4 papers · 2 filters

cs.DS2021

Fixed-Parameter Sensitivity Oracles

Davide Bilò, Katrin Casel, Keerti Choudhary +5

We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f…

cs.DS2021

Space-Efficient Fault-Tolerant Diameter Oracles

Davide Bilò, Sarel Cohen, Tobias Friedrich +1

We design $f$ -edge fault-tolerant diameter oracles ( $f$ -FDOs). We preprocess a given graph $G$ on $n$ vertices and $m$ edges, and a positive integer $f$ , to construct a data struct…

cs.DS2021

Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles

Davide Bilò, Sarel Cohen, Tobias Friedrich +1

Given a graph with a source vertex $s$ , the Single Source Replacement Paths (SSRP) problem is to compute, for every vertex $t$ and edge $e$ , the length $d (s, t, e)$ of a shortest pat…

cs.DS2021

Finding single-source shortest $p$ -disjoint paths: fast computation and sparse preservers

Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà +3

Let $G$ be a directed graph with $n$ vertices, $m$ edges, and non-negative edge costs. Given $G$ , a fixed source vertex $s$ , and a positive integer $p$ , we consider the problem of…

Fixed-Parameter Sensitivity Oracles

Space-Efficient Fault-Tolerant Diameter Oracles

Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles

Finding single-source shortest p-disjoint paths: fast computation and sparse preservers

Finding single-source shortest $p$ -disjoint paths: fast computation and sparse preservers