Computing maximum mean cuts (Q1329796)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 612422
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Computing maximum mean cuts |
scientific article; zbMATH DE number 612422 |
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
0.7993081212043762
0 references
0.7892618775367737
0 references
0.7887915372848511
0 references
0.7849380373954773
0 references
