10 citations · 15 across the 17 of their papers we have counts for
5 papers · 1 filter
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…
Temporal Network Creation Games
Davide Bilò, Sarel Cohen, Tobias Friedrich +4
Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs…
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…