Victor Valls, Panagiotis Promponas, et al.
IEEE Communications Magazine
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
Conference paper
Social networks and discovery in the enterprise (SaND)
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Qing Li, Zhigang Deng, et al.
IEEE T-MI