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
∙
02/22/2023
Fair Correlation Clustering in Forests
The study of algorithmic fairness received growing attention recently. T...
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
∙
07/07/2021
Space-Efficient Fault-Tolerant Diameter Oracles
We design f-edge fault-tolerant diameter oracles (f-FDOs). We preprocess...
research
∙
06/29/2021
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Given a graph with a source vertex s, the Single Source Replacement Path...
research
∙
03/24/2021
The Complexity of Dependency Detection and Discovery in Relational Databases
Multi-column dependencies in relational databases come associated with t...
research
∙
07/15/2020
timeXplain – A Framework for Explaining the Predictions of Time Series Classifiers
Modern time series classifiers display impressive predictive capabilitie...
research
∙
10/01/2019
The Minimization of Random Hypergraphs
We investigate the maximum-entropy model B_n,m,p for random n-vertex, m-...
research
∙
05/29/2019
Understanding the Effectiveness of Data Reduction in Public Transportation Networks
Given a public transportation network of stations and connections, we wa...
research
∙
05/03/2018
