Koustav Bhanja

activity

20242026

collaborators

6 papers

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

Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracle

Surender Baswana, Koustav Bhanja

Let G be a directed weighted graph (DiGraph) on n vertices and m edges with source s and sink t. An edge in G is vital if its removal reduces the capacity of (s,t)-mincut. Since th…

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…