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

B.K. Boguraev, Mary S. Neff

HICSS 2000

Paper

Matthias Kaiserswerth

IEEE/ACM Transactions on Networking

Conference paper

Thomas R. Puzak, A. Hartstein, et al.

CF 2007

Paper

Charles H. Bennett, Aram W. Harrow, et al.

IEEE Trans. Inf. Theory