18 citations · 23 across the 12 of their papers we have counts for
6 papers · 1 filter
Improved Distance (Sensitivity) Oracles with Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
A distance oracle (DO) with stretch for a graph is a data structure that, when queried with vertices and , returns a value such that $d(s,t)…
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners wi…
Finding Diameter-Reducing Shortcuts in Trees
Davide Bilò, Luciano Gualà, Stefano Leucci +1
In the \emph{-Diameter-Optimally Augmenting Tree Problem} we are given a tree of vertices as input. The tree is embedded in an unknown \emph{metric} space and we have un…
Compact Distance Oracles with Large Sensitivity and Low Stretch
Davide Bilò, Keerti Choudhary, Sarel Cohen +3
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses an input graph . When queried with the triple $(s,t,F…
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…
Compact and Fast Sensitivity Oracles for Single-Source Distances
Davide Bilò, Luciano Gualà, Stefano Leucci +1
Let denote a distinguished source vertex of a non-negatively real weighted and undirected graph with vertices and edges. In this paper we present two efficient \emp…