Parallel algorithms for minimum cuts and maximum flows in planar networks
- 1 October 1987
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 34 (4) , 950-967
- https://doi.org/10.1145/31846.31849
Abstract
Algorithms are given that compute maximum flows in planar directed networks either in O ((log n ) 3 ) parallel time using O ( n 4 ) processors or O ((log n ) 2 ) parallel time using O ( n 6 ) processors. The resource consumption of these algorithms is dominated by the cost of finding the value of a maximum flow. When such a value is given, or when the computation is on an undirected network, the bound is O ((log n ) 2 ) time using O ( n 3 ) processors. No efficient parallel algorithm is known for the maximum flow problem in general networks.Keywords
This publication has 7 references indexed in Scilit:
- A note on finding minimum cuts in directed planar networks by parallel computationsInformation Processing Letters, 1985
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar NetworksSIAM Journal on Computing, 1985
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ TimeSIAM Journal on Computing, 1983
- The maximum flow problem is log space complete for PTheoretical Computer Science, 1982
- An O(n2log n) parallel max-flow algorithmJournal of Algorithms, 1982
- Maximum flow in (s,t) planar networksInformation Processing Letters, 1981
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969