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

CREATORSurender Baswana, Koustav Bhanja, Anupam Roy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE135 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-01366

Browse the full library · About the Tower of Babel