Chaitanya Nalam

activity

20232026

k

-Vertex Connectivity in

k^{2}

Max-flows

2 citations · 2 across the 4 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2025

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 $n$ vertices and $m$ edges in $O (mn)$ time. This breaks the long-sta…

cs.DS2023★ 2 cited

Deterministic $k$ -Vertex Connectivity in $k^{2}$ Max-flows

Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

An $n$ -vertex $m$ -edge graph is \emph{ $k$ -vertex connected} if it cannot be disconnected by deleting less than $k$ vertices. After more than half a century of intensive research, t…

cs.DS2023

Maximal $k$ -Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction

Chaitanya Nalam, Thatchaphol Saranurak

The \emph{maximal $k$ -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…

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness

Deterministic k-Vertex Connectivity in k2 Max-flows

Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction

Deterministic $k$ -Vertex Connectivity in $k^{2}$ Max-flows

Maximal $k$ -Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction