On the Number of Small Cuts in a Graph
Permanent Link(s)
Collections
Author
Henzinger, Monika Rauch
Williamson, David
Abstract
We prove that in an undirected graph there are at most $O(n^2)$ cuts of size strictly less than $\frac{3}{2}$ the size of the minimum cut.
Date Issued
1995-02
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1486
Type
technical report