### Parallel algorithms for minimum cuts and maximum flows in planar networksParallel algorithms for minimum cuts and maximum flows in planar networks

Access Restriction
Subscribed

 Author Johnson, Donald B. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Algorithms are given that compute maximum flows in planar directed networks either in $\textit{O}((log$ $\textit{n})3)$ parallel time using $\textit{O}(\textit{n}4)$ processors or $\textit{O}((log$ $\textit{n})2)$ parallel time using $\textit{O}(\textit{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 $\textit{O}((log$ $\textit{n})2)$ time using $\textit{O}(\textit{n}3)$ processors. No efficient parallel algorithm is known for the maximum flow problem in general networks. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1987-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 4 Page Count 18 Starting Page 950 Ending Page 967

#### Open content in new tab

Source: ACM Digital Library