Showing 2025Show all
2 papers · 1 filter
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 (or less) vertex failures occur. An -FT Ste…