Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Paper
On the number of small cuts in a graph
Abstract
We prove that in an undirected graph there are at most O(n2) cuts of size strictly less than 3/2 of the size of the minimum cut.
Related
G. Ramalingam
Theoretical Computer Science
Conference paper
Global routing revisited
Michael D. Moffitt
ICCAD 2009
Conference paper
COUNTERFACTUAL CONCEPT BOTTLENECK MODELS
Gabriele Dominici, Pietro Barbiero, et al.
ICLR 2025