research
∙
11/08/2022
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
We provide the first deterministic data structure that given a weighted ...
share
research
∙
09/19/2022
A Simple Framework for Finding Balanced Sparse Cuts via APSP
We present a very simple and intuitive algorithm to find balanced sparse...
research
∙
08/23/2022
Derandomizing Directed Random Walks in Almost-Linear Time
In this article, we present the first deterministic directed Laplacian L...
research
∙
04/05/2022
Maintaining Expander Decompositions via Sparse Cuts
In this article, we show that the algorithm of maintaining expander deco...
research
∙
03/01/2022
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
We give an algorithm that computes exact maximum flows and minimum-cost ...
research
∙
02/10/2022
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
We study linear equations in combinatorial Laplacians of k-dimensional s...
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
∙
10/22/2021
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Given a directed, weighted graph G=(V,E) undergoing edge insertions, the...
research
∙
01/18/2021
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
In the decremental single-source shortest paths problem, the goal is to ...
research
∙
11/27/2020
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
In this thesis, we present new techniques to deal with fundamental algor...
research
∙
10/20/2020
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Maintaining and updating shortest paths information in a graph is a fund...
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/05/2020
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Let G = (V,E,w) be a weighted, digraph subject to a sequence of adversar...
research
∙
04/17/2020
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Designing dynamic graph algorithms against an adaptive adversary is a ma...
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/29/2020
