5,323
edits
Parallel Algorithms: Difference between revisions
→Randomized Symmetry Breaking
| Line 466: | Line 466: | ||
s(i) = 1 | s(i) = 1 | ||
</pre> | </pre> | ||
;Notes | |||
* The full randomized list ranking works in <math>O(\log n \log\log n)</math> time and <math>O(n)</math> work with high probability | |||
===Deterministic Symmetry Breaking=== | ===Deterministic Symmetry Breaking=== | ||