On the number of small cuts in a graph

Paper

08 Jul 1996

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.

Conference paper

Yun Mao, Hani Jamjoom, et al.

CoNEXT 2006

Conference paper

Maurice Hanan, Peter K. Wolff, et al.

DAC 1976

Conference paper

Erich P. Stuntebeck, John S. Davis II, et al.

HotMobile 2008

Workshop paper

Robert G. Farrell, Catalina M. Danis, et al.

RecSys 2012