6 citations · 20 across the 19 of their papers we have counts for
4 papers · 2 filters
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)$…
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 ,…
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…