research
∙
07/21/2023
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Despite extensive research on distance oracles, there are still large ga...
share
research
∙
05/19/2023
Approximate Distance Sensitivity Oracles in Subquadratic Space
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch ...
research
∙
05/05/2023
Fault-Tolerant ST-Diameter Oracles
We study the problem of estimating the ST-diameter of a graph that is su...
research
∙
04/27/2023
Compact Distance Oracles with Large Sensitivity and Low Stretch
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch ...
research
∙
04/22/2022
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
We construct data structures for extremal and pairwise distances in dire...
research
∙
12/06/2021
Fixed-Parameter Sensitivity Oracles
We combine ideas from distance sensitivity oracles (DSOs) and fixed-para...
research
∙
10/22/2021
Pairwise Reachability Oracles and Preservers under Failures
In this paper, we consider reachability oracles and reachability preserv...
research
∙
07/07/2021
Budgeted Dominating Sets in Uncertain Graphs
We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, ...
research
∙
04/27/2020
New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures
In this paper, we consider the question of computing sparse subgraphs fo...
research
∙
02/13/2020
Distributed Graph Realizations
We study graph realization problems from a distributed perspective and w...
research
∙
12/31/2019
Efficiently Realizing Interval Sequences
We consider the problem of realizable interval-sequences. An interval se...
research
∙
12/31/2019
Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods
The classical problem of degree sequence realizability asks whether or n...
research
∙
12/04/2018