Simon Krogmann

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2023

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…