On the number of small cuts in a graph
Henzinger M, Williamson DP. 1996. On the number of small cuts in a graph. Information Processing Letters. 59(1), 41–44.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA 
;
Williamson, David P.
;
Williamson, David P.Abstract
We prove that in an undirected graph there are at most O(n²) cuts of size strictly less than of the size of the minimum cut.
Publishing Year
Date Published
1996-07-08
Journal Title
Information Processing Letters
Publisher
Elsevier
Volume
59
Issue
1
Page
41-44
ISSN
IST-REx-ID
Cite this
Henzinger M, Williamson DP. On the number of small cuts in a graph. Information Processing Letters. 1996;59(1):41-44. doi:10.1016/0020-0190(96)00079-8
Henzinger, M., & Williamson, D. P. (1996). On the number of small cuts in a graph. Information Processing Letters. Elsevier. https://doi.org/10.1016/0020-0190(96)00079-8
Henzinger, Monika, and David P. Williamson. “On the Number of Small Cuts in a Graph.” Information Processing Letters. Elsevier, 1996. https://doi.org/10.1016/0020-0190(96)00079-8.
M. Henzinger and D. P. Williamson, “On the number of small cuts in a graph,” Information Processing Letters, vol. 59, no. 1. Elsevier, pp. 41–44, 1996.
Henzinger M, Williamson DP. 1996. On the number of small cuts in a graph. Information Processing Letters. 59(1), 41–44.
Henzinger, Monika, and David P. Williamson. “On the Number of Small Cuts in a Graph.” Information Processing Letters, vol. 59, no. 1, Elsevier, 1996, pp. 41–44, doi:10.1016/0020-0190(96)00079-8.
Google Scholar