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.
Details
Title
On the number of small cuts in a graph
Author(s)
Henzinger, Monika ; Williamson, David P.
Published in
Information Processing Letters
Volume
59
Issue
1
Pages
41-44
Date
1996
Keywords
Other identifier(s)
View record in Scopus
Laboratories
LTAA
Record Appears in
Scientific production and competences > I&C - School of Computer and Communication Sciences > IC Archives > LTAA - Laboratory of Theory and Applications of Algorithms
Peer-reviewed publications
Work outside EPFL
Journal Articles
Published
Peer-reviewed publications
Work outside EPFL
Journal Articles
Published
Record creation date
2007-01-18