215 citations · 689 across the 60 of their papers we have counts for
10 papers · 1 filter
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Sagnik Mukhopadhyay, Danupon Nanongkai
Consider the following 2-respecting min-cut problem. Given a weighted graph and its spanning tree , find the minimum cut among the cuts that contain at most two edges in …
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)$…
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
Jan van den Brand, Danupon Nanongkai
Consider the following distance query for an -node graph undergoing edge insertions and deletions: given two sets of nodes and , return the distances between every pa…
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…
A New Deterministic Algorithm for Dynamic Set Cover
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
We present a deterministic dynamic algorithm for maintaining a -approximate minimum cost set cover with amortized update time, when the input set system…