5 papers
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay +1
Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed varian…
Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
Yonggang Jiang, Changki Yun
We present a randomized parallel algorithm in the {\sf PRAM} model for -vertex connectivity. Given an undirected simple graph, our algorithm either finds a set of fewer than …
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak +1
We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph vertices and edges in time. This breaks the long-sta…
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay +1
A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequ…
Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang +1
For -vertex -edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with $\tilde O(m…