5,350
edits
Parallel Algorithms: Difference between revisions
→Work-optimal List Ranking
| Line 397: | Line 397: | ||
===Work-optimal List Ranking=== | ===Work-optimal List Ranking=== | ||
* From our list A, pull a subset S with uniform density and sparcity | |||
* Remove S from A, creating a new subset <math>A-S</math>. | |||
** For each element i in <math>S</math>, fix the next and distance of prev(i) | |||
** Run compaction | |||
* Recurse on <math>A-S</math> until size is <math>\leq n/\log n</math>. Then use pointer jumping. | |||
* Add <math>S</math> back to <math>A-S</math> | |||
===Randomized Symmetry Breaking=== | |||
<pre> | <pre> | ||
for i 1 <= i <= n pardo | for i 1 <= i <= n pardo | ||