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 · 2025
Read Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut by Surender Baswana, Koustav Bhanja, Anupam Roy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01366.txt.
Description
Surender Baswana, Koustav Bhanja, and Anupam Roy study cuts in networks, a core topic in computer science. A cut splits a network so a start point and an end point fall on opposite sides, and the cheapest such split is the mincut. They focus on the second-cheapest split, which matters for backup planning when the best route fails. A 1992 method needed many flow computations to find it.
For directed, weighted networks, their algorithm needs only the square root of that count, a major saving. The trick rests on a new link between second-best splits and the cheapest global cut. They speed up work on near-cheapest cuts and build a compact structure storing all of them in less space. Finally, they break a known space barrier for data structures that answer what happens when two links fail at once.
Catalog record
| CREATOR | Surender Baswana, Koustav Bhanja, Anupam Roy |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 135 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01366