215 citations · 318 across the 83 of their papers we have counts for
10 papers · 1 filter
Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak
The dynamic optimality conjecture, postulating the existence of an -competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems i…
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak +2
Consider the following "local" cut-detection problem in a directed graph: We are given a seed vertex and need to remove at most edges so that at most edges can be reach…
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
Yu Gao, Jason Li, Danupon Nanongkai +3
We study deterministic algorithms for computing graph cuts, with focus on two fundamental problems: balanced sparse cut and -vertex connectivity for small ($k=O(\polylog n)$…
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
Julia Chuzhoy, Yu Gao, Jason Li +3
We consider the classical Minimum Balanced Cut problem: given a graph , compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number…
Sensitive Distance and Reachability Oracles for Large Batch Updates
Jan van den Brand, Thatchaphol Saranurak
In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph with nodes and integer weights from . Second, given a s…
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
Yi-Jun Chang, Thatchaphol Saranurak
An -expander decomposition of a graph is a clustering of the vertices such that (1) each cluster induces subgraph with conduc…
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak
The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynam…
Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
We present a new, simple, algorithm for the local vertex connectivity problem (LocalVC) introduced by Nanongkai~et~al. [STOC'19]. Roughly, given an undirected unweighted graph ,…
Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, Danupon Nanongkai +1
We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity exactly in the CONGEST model, as long as there are no…
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Vertex connectivity a classic extensively-studied problem. Given an integer , its goal is to decide if an -node -edge graph can be disconnected by removing vertices. A…