๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts

โœ Scribed by Liang Zhao; Hiroshi Nagamochi; Toshihide Ibaraki

Book ID
110303903
Publisher
Springer US
Year
2001
Tongue
English
Weight
329 KB
Volume
5
Category
Article
ISSN
1382-6905

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the Number of Minimum Cuts in a Graph
On the Number of Minimum Cuts in a Graph
โœ Chandran, L. Sunil; Ram, L. Shankar ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Society for Industrial and Applied Mathematics ๐ŸŒ English โš– 253 KB
A Faster Algorithm for Finding the Minim
A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
โœ J.X. Hao; J.B. Orlin ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 995 KB

We consider the problem of finding the minimum capacity cut in a directed network \(G\) with \(n\) nodes. This problem has applications to network reliability and survivability and is useful in subroutines for other network optimization problems. One can use a maximum flow problem to find a minimum

The number of cut-vertices in a graph of
The number of cut-vertices in a graph of given minimum degree
โœ Michael O. Albertson; David M. Berman ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 228 KB

Albertson, M.O. and D.M. Berman, The number of cut-vertices in a graph of given minimum degree, Discrete Mathematics 89 (1991) 97-100. A graph with n vertices and minimum degree k 2 2 can contain no more than (2k -2)n/(kz -2) cut-vertices. This bound is asymptotically tight. \* Research supported in