Keerti Choudhary

activity

20112026

most citedDynamic DFS Tree in Undirected Graphs: breaking the

O (m)

barrier

14 citations · 19 across the 13 of their papers we have counts for

collaborators

Showing 2023Show all

4 papers · 1 filter

cs.DS2023

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…

cs.DS2023★ 2 cited

Approximate Distance Sensitivity Oracles in Subquadratic Space

Davide Bilò, Shiri Chechik, Keerti Choudhary +4

An $f$ -edge fault-tolerant distance sensitive oracle ( $f$ -DSO) with stretch $σ \geq 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertice…

cs.DS2023

Fault-Tolerant ST-Diameter Oracles

Davide Bilò, Keerti Choudhary, Sarel Cohen +3

Given two vertex sets $S$ and $T$ in a graph, the $S T$ -diameter is the maximum $s$ - $t$ -distance between vertices $s \in S$ and $t \in T$ . We study the problem of estimating the $ST…

cs.DS2023

Compact Distance Oracles with Large Sensitivity and Low Stretch

Davide Bilò, Keerti Choudhary, Sarel Cohen +3

An $f$ -edge fault-tolerant distance sensitive oracle ( $f$ -DSO) with stretch $σ \geq 1$ is a data structure that preprocesses an input graph $G$ . When queried with the triple $(s,t,F…