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.
Titre
On the number of small cuts in a graph
Publié dans
Information Processing Letters
Volume
59
Numéro
1
Pages
41-44
Date
1996
Date de création de la notice
2007-01-18