𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Faster Algorithm for Finding the Minimum Cut in a Directed Graph

✍ Scribed by J.X. Hao; J.B. Orlin

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
995 KB
Volume
17
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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 cut separating a designated source node (s) from a designated sink node (t), and by varying the sink node one can find a minimum cut in (G) as a sequence of at most (2 n-2) maximum flow problems. We then show how to reduce the running time of these (2 n-2) maximum flow algorithms to the running time for solving a single maximum flow problem. The resulting running time is (O\left(n m \log \left(n^{2} / m\right)\right)) for finding the minimum cut in either a directed or an undirected network. (\mathbb{C} 1994) Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

A comparison of three algorithms for fin
A comparison of three algorithms for finding fundamental cycles in a directed graph
✍ Doris R. Ryan; Stephen Chen πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 543 KB

## Abstract Given a connected directed graph and a spanning tree, we consider the problem of finding the set of fundamental cycles. In particular, for each cotree arc __i__ and tree arc __j__, we need to know whether or not __i__ and __j__ are in the same fundamental cycle, and if so, whether or no

A branch and cut algorithm for the Stein
A branch and cut algorithm for the Steiner problem in graphs
✍ Lucena, A.; Beasley, J. E. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 165 KB πŸ‘ 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

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