Loading...
Please wait, while we are loading the content...
Similar Documents
An Optimal Randomized Logarithmic Time Connectivity Algorithm for the EREW PRAM (Extended Abstract) (1994)
| Content Provider | CiteSeerX |
|---|---|
| Author | Halperin, Shay Zwick, Uri |
| Abstract | Shay Halperin Uri Zwick Department of Computer Science Tel Aviv University Tel Aviv, 69978 Israel Abstract Improving a long chain of works we obtain a randomized EREW PRAM algorithm for nding the connected components of a graph G = (V; E) with n vertices and m edges in O(log n) time using an optimal number of O((m+n)= log n) processors. The result returned by the algorithm is always correct. The probability that the algorithm will not complete in O(log n) time is at most n for any desired c > 0. The best deterministic EREW PRAM connectivity algorithm, obtained by Chong and Lam, runs in O(log n log log n) time using m+ n processors. |
| File Format | |
| Publisher Date | 1994-01-01 |
| Access Restriction | Open |
| Subject Keyword | Deterministic Erew Pram Connectivity Algorithm Israel Abstract Shay Halperin Uri Zwick Department Long Chain Erew Pram Randomized Erew Pram Algorithm |
| Content Type | Text |
