research
∙
08/09/2023
Deterministic k-Vertex Connectivity in k^2 Max-flows
An n-vertex m-edge graph is k-vertex connected if it cannot be disconnec...
share
research
∙
07/05/2023
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
We consider the problem of comparison-sorting an n-permutation S that av...
research
∙
11/08/2022
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Greedy BST (or simply Greedy) is an online self-adjusting binary search ...
research
∙
10/25/2022
Deterministic Small Vertex Connectivity in Almost Linear Time
In the vertex connectivity problem, given an undirected n-vertex m-edge ...
research
∙
05/30/2022
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is t...
research
∙
03/31/2021
Vertex Connectivity in Poly-logarithmic Max-flows
The vertex connectivity of an m-edge n-vertex undirected graph is the sm...
research
∙
03/29/2021
Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity
Vertex connectivity is a well-studied concept in graph theory with numer...
research
∙
10/31/2019
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Consider the following "local" cut-detection problem in a directed graph...
research
∙
10/17/2019
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
We study deterministic algorithms for computing graph cuts, with focus o...
research
∙
05/14/2019
Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries
We present a new, simple, algorithm for the local vertex connectivity pr...
research
∙
04/09/2019