Koustav Bhanja

activity

20232026

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2026

Space-Optimal Sensitivity Oracles for Single-Source Mincuts

Koustav Bhanja, Merav Parter, Asaf Petruschka

We study Single-Source Mincut Sensitivity Oracles: compact data structures that, when queried with an edge e, report those affected vertices whose mincut value to source $s$ change…

cs.DS2025

Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut

Surender Baswana, Koustav Bhanja, Anupam Roy

We study (s,t)-cuts of second minimum capacity and present the following algorithmic and graph-theoretic results. 1. Vazirani and Yannakakis [ICALP 1992] designed the first algorit…

cs.DS2025

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity

Koustav Bhanja, Asaf Petruschka

We present a compact labeling scheme for determining whether a designated set of terminals in a graph remains connected after any $f$ (or less) vertex failures occur. An $f$ -FT Ste…

cs.DS2024

Optimal Sensitivity Oracle for Steiner Mincut

Koustav Bhanja

Let $G = (V, E)$ be an undirected weighted graph on $n = ∣ V ∣$ vertices and $S \subseteq V$ be a Steiner set. Steiner mincut is a well-studied concept, which provides a generalization to…

cs.DS2024

Minimum+1 Steiner Cuts and Dual Edge Sensitivity Oracle: Bridging the Gap between Global cut and (s,t)-cut

Koustav Bhanja

Let $G = (V, E)$ be an undirected multi-graph on $n = ∣ V ∣$ vertices and $S \subseteq V$ be a Steiner set. Steiner cut is a fundamental concept; moreover, global cut $(∣ S ∣ = n)$ , as well as…