Showing 2026Show all
2 papers · 1 filter
cs.DS2026
An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions
Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka
Given an undirected weighted graph on vertices, the classical Gomory-Hu tree of is a structure that encodes an arbitrary minimum -cut for every us…
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 change…