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

Yvonne Anne Pignolet, Stefan Schmid, et al.

Discrete Mathematics and Theoretical Computer Science

Conference paper

Kaoutar El Maghraoui, Gokul Kandiraju, et al.

WOSP/SIPEW 2010

Conference paper

Pradip Bose

VTS 1998

Conference paper

Raghu Krishnapuram, Krishna Kummamuru

IFSA 2003