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.

Paper

Ruixiong Tian, Zhe Xiang, et al.

Qinghua Daxue Xuebao/Journal of Tsinghua University

Paper

György E. Révész

Theoretical Computer Science

Conference paper

Renu Tewari, Richard P. King, et al.

IS&T/SPIE Electronic Imaging 1996

Conference paper

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

HotMobile 2008