Authors
Citation
M. Henzinger et Dp. Williamson, ON THE NUMBER OF SMALL CUTS IN A GRAPH, Information processing letters, 59(1), 1996, pp. 41-44
Citations number
3
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
ISSN journal
00200190
Volume
59
Issue
1
Year of publication
1996
Pages
41 - 44
Database
ISI
SICI code
0020-0190(1996)59:1<41:OTNOSC>2.0.ZU;2-F
Abstract
We prove that in an undirected graph there are at most O(n(2)) cuts of
size strictly less than 3/2 of the size of the minimum cut.