215 citations · 318 across the 83 of their papers we have counts for
7 papers · 1 filter
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
A cactus representation of a graph, introduced by Dinitz et al. in 1976, is an edge sparsifier of size that exactly captures all global minimum cuts of the graph. It is a ce…
Deterministic -Vertex Connectivity in Max-flows
Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
An -vertex -edge graph is \emph{-vertex connected} if it cannot be disconnected by deleting less than vertices. After more than half a century of intensive research, t…
Maximal -Edge-Connected Subgraphs in Almost-Linear Time for Small
Thatchaphol Saranurak, Wuwei Yuan
We give the first almost-linear time algorithm for computing the \emph{maximal -edge-connected subgraphs} of an undirected unweighted graph for any constant . More specifical…
Chasing Positive Bodies
Sayan Bhattacharya, Niv Buchbinder, Roie Levin +1
We study the problem of chasing positive bodies in : given a sequence of bodies revealed online…
Maximal -Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction
Chaitanya Nalam, Thatchaphol Saranurak
The \emph{maximal -edge-connected subgraphs} problem is a classical graph clustering problem studied since the 70's. Surprisingly, no non-trivial technique for this problem in w…
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Gramoz Goranci, Monika Henzinger, Danupon Nanongkai +3
Given a simple -vertex, -edge graph undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G…
Dynamic -Approximate Matching Size in Truly Sublinear Update Time
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
We show a fully dynamic algorithm for maintaining -approximate \emph{size} of maximum matching of the graph with vertices and edges using update tim…