Thomas M. Cheng
IT Professional
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
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006