English
Français
login
Menu
Search
Browse Collections
Help
English
Français
login
On the number of small cuts in a graph
Henzinger, Monika
;
Williamson, David P.
1996
Formats
Format
BibTeX
View
Download
MARC
View
Download
MARCXML
View
Download
DublinCore
View
Download
EndNote
View
Download
NLM
View
Download
RefWorks
View
Download
RIS
View
Download
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
Algorithms
;
Cuts in a graph
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