Computing maximum mean cuts (Q1329796)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computing maximum mean cuts |
scientific article |
Statements
Computing maximum mean cuts (English)
0 references
31 July 1994
0 references
A strongly polynomial parametric algorithm for computing a maximum mean cut in a directed network is discussed. It needs at most \(O(n)\) min cut calculations. This algorithm provides the missing component in a strongly polynomial minimum cost network flow algorithm based on cancelling maximum mean cuts developed by the authors earlier. Several other algorithms for computing maximum mean cuts are reviewed.
0 references
maximum mean cut
0 references
directed network
0 references
strongly polynomial minimum cost network flow algorithm
0 references
0 references
0 references
0 references
