Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
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
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research
Xiaozhu Kang, Hui Zhang, et al.
ICWS 2008