Chaitanya Nalam

activity

20232026

k

-Vertex Connectivity in

k^{2}

Max-flows

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

collaborators

3 papers

math.CO2026

Joins and ear decompositions beyond graphic matroids

Yuhang Bai, Kristóf Bérczi, Chaitanya Nalam

For a matroid $M$ , a join is a set $J \subseteq E (M)$ that meets every circuit $C$ in at most $∣ C ∣/2$ elements. Let $μ (M)$ denote the maximum size of a join. Motivated by Frank's mi…

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…

Joins and ear decompositions beyond graphic matroids

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness

Deterministic k-Vertex Connectivity in k2 Max-flows

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