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

4 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…

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…

Joins and ear decompositions beyond graphic matroids

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