research
∙
04/04/2023
VC Set Systems in Minor-free (Di)Graphs and Applications
A recent line of work on VC set systems in minor-free (undirected) graph...
share
research
∙
02/12/2023
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Given a simple n-vertex, m-edge graph G undergoing edge insertions and d...
research
∙
03/07/2022
Negative-Weight Single-Source Shortest Paths in Near-linear Time
We present a randomized algorithm that computes single-source shortest p...
research
∙
11/14/2021
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs
Given an n-vertex planar embedded digraph G with non-negative edge weigh...
research
∙
11/05/2021
Optimal Approximate Distance Oracle for Planar Graphs
A (1+ϵ)-approximate distance oracle of an edge-weighted graph is a data ...
research
∙
09/30/2021
Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs
Given an undirected n-vertex planar graph G=(V,E,ω) with non-negative ed...
research
∙
12/21/2020
Escaping an Infinitude of Lions
We consider the following game played in the Euclidean plane: There is a...
research
∙
10/02/2020
Decremental APSP in Directed Graphs Versus an Adaptive Adversary
Given a directed graph G = (V,E), undergoing an online sequence of edge ...
research
∙
09/30/2020
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs
Given an undirected, unweighted planar graph G with n vertices, we prese...
research
∙
04/09/2020
Near-Optimal Decremental SSSP in Dense Weighted Digraphs
In the decremental Single-Source Shortest Path problem (SSSP), we are gi...
research
∙
01/29/2020
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
Given a dynamic digraph G = (V,E) undergoing edge deletions and given s∈...
research
∙
01/29/2020
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
In the decremental (1+ϵ)-approximate Single-Source Shortest Path (SSSP) ...
research
∙
01/29/2020
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
Given a directed weighted graph G=(V,E) undergoing vertex insertions and...
research
∙
01/11/2019
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Computing the Strongly-Connected Components (SCCs) in a graph G=(V,E) is...
research
∙
12/13/2017
Greedy spanners are optimal in doubling metrics
We show that the greedy spanner algorithm constructs a (1+ϵ)-spanner of ...
research
∙
11/02/2017
