Simon Krogmann

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2026

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.DS2024

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 $I ¨ \geq 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertic…