On the number of small cuts in a graph
Henzinger, Monika; Williamson, David P.
1996

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
DOI https://doi.org/10.1016/0020-0190(96)00079-8
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
Record creation date 2007-01-18

Actions