A note on finding minimum cuts in directed planar networks by parallel computations (Q1069429)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A note on finding minimum cuts in directed planar networks by parallel computations |
scientific article; zbMATH DE number 3934731
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on finding minimum cuts in directed planar networks by parallel computations |
scientific article; zbMATH DE number 3934731 |
Statements
A note on finding minimum cuts in directed planar networks by parallel computations (English)
0 references
1985
0 references
It is shown that the minimum cut in general planar networks can be found in O((log n)\({}^ 2)\) time by \(O(n^ 4)\) processors. The processor bound can be improved to \(O(n^ 3)\) when the network is embedded in the plane beforehand.
0 references
parallel algorithm
0 references
minimum cut
0 references
general planar networks
0 references
