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...
share
research
∙
02/10/2023
Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time
We show a fully dynamic algorithm for maintaining (1+ϵ)-approximate size...
research
∙
07/15/2022
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
We present dynamic algorithms with polylogarithmic update time for estim...
research
∙
03/01/2022
Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time
In this paper, we introduce a robust notion of (1+ϵ)-approximate (s, t)-...
research
∙
11/17/2021
Minimum Cuts in Directed Graphs via Partial Sparsification
We give an algorithm to find a minimum cut in an edge-weighted directed ...
research
∙
11/09/2021
Gomory-Hu Tree in Subcubic Time
In 1961, Gomory and Hu showed that the max-flow values of all n 2 pairs ...
research
∙
04/16/2021
Minimum Cuts in Directed Graphs via √(n) Max-Flows
We give an algorithm to find a mincut in an n-vertex, m-edge weighted di...
research
∙
09/17/2020
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition
In the decremental single-source shortest paths (SSSP) problem, the inpu...
research
∙
10/17/2019
