
A Nearly Optimal AllPairs MinCuts Algorithm in Simple Graphs
We give an n^2+o(1)time algorithm for finding st mincuts for all pair...
read it

Deterministic Weighted Expander Decomposition in Almostlinear Time
In this note, we study the expander decomposition problem in a more gene...
read it

Minimum Cuts in Directed Graphs via √(n) MaxFlows
We give an algorithm to find a mincut in an nvertex, medge weighted di...
read it

Vertex Connectivity in Polylogarithmic Maxflows
The vertex connectivity of an medge nvertex undirected graph is the sm...
read it

Deterministic Decremental SSSP and Approximate MinCost Flow in AlmostLinear Time
In the decremental singlesource shortest paths problem, the goal is to ...
read it

Minimum Cost Flows, MDPs, and ℓ_1Regression in Nearly Linear Time for Dense Instances
In this paper we provide new randomized algorithms with improved runtime...
read it

Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition
In the decremental singlesource shortest paths (SSSP) problem, the inpu...
read it

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...
read it

Bipartite Matching in Nearlylinear Time on Moderately Dense Graphs
We present an Õ(m+n^1.5)time randomized algorithm for maximum cardinali...
read it

A Simple Deterministic Algorithm for Edge Connectivity
We show a deterministic algorithm for computing edge connectivity of a s...
read it

Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
There is a recent exciting line of work in distributed graph algorithms ...
read it

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
We introduce a notion for hierarchical graph clustering which we call th...
read it

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
We present a general framework of designing efficient dynamic approximat...
read it

FullyDynamic Graph Sparsifiers Against an Adaptive Adversary
Designing dynamic graph algorithms against an adaptive adversary is a ma...
read it

CoarseGrained Complexity for Dynamic Algorithms
To date, the only way to argue polynomial lower bounds for dynamic algor...
read it

Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
The famous dynamic optimality conjecture of Sleator and Tarjan from 1985...
read it

Computing and Testing Small Connectivity in NearLinear Time and Queries via Fast Local Cut Algorithms
Consider the following "local" cutdetection problem in a directed graph...
read it

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
We consider the classical Minimum Balanced Cut problem: given a graph G,...
read it

Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and kVertex
We study deterministic algorithms for computing graph cuts, with focus o...
read it

Sensitive Distance and Reachability Oracles for Large Batch Updates
In the sensitive distance oracle problem, there are three phases. We fir...
read it

Computing and Testing Small Vertex Connectivity in NearLinear Time and Queries
We present a new, simple, algorithm for the local vertex connectivity pr...
read it

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
The dynamic matrix inverse problem is to maintain the inverse of a matri...
read it

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
An (ϵ,ϕ)expander decomposition of a graph G=(V,E) is a clustering of th...
read it

Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Vertex connectivity a classic extensivelystudied problem. Given an inte...
read it

Distributed Edge Connectivity in Sublinear Time
We present the first sublineartime algorithm for a distributed message...
read it

Expander Decomposition and Pruning: Faster, Stronger, and Simpler
We study the problem of graph clustering where the goal is to partition ...
read it

Multifinger binary search trees
We study multifinger binary search trees (BSTs), a farreaching extensi...
read it

Smooth heaps and a dual view of selfadjusting data structures
We present a new connection between selfadjusting binary search trees (...
read it
Thatchaphol Saranurak
is this you? claim profile