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

Robert E. Donovan

INTERSPEECH - Eurospeech 2001

Conference paper

Lerong Cheng, Jinjun Xiong, et al.

ASP-DAC 2008

Conference paper

Pradip Bose

VTS 1998

Conference paper

Xiaozhu Kang, Hui Zhang, et al.

ICWS 2008