On the number of small cuts in a graph

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.


Published in:
Inf. Process. Lett., 59, 1, 41-44
Year:
1996
Keywords:
Other identifiers:
Scopus: 2-s2.0-0040203288
Laboratories:




 Record created 2007-01-18, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)