18 citations · 44 across the 26 of their papers we have counts for
5 papers · 2 filters
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…
Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +4
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses a given undirected, unweighted graph with vertice…
Fault-Tolerant ST-Diameter Oracles
Davide Bilò, Keerti Choudhary, Sarel Cohen +3
Given two vertex sets and in a graph, the -diameter is the maximum --distance between vertices and . We study the problem of estimating the $ST…
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…