5,323
edits
Parallel Algorithms: Difference between revisions
→r-ruling set
| Line 438: | Line 438: | ||
;Algorithm | ;Algorithm | ||
The following algorithm gives us an r-ruling set with <math>r=2*\log n - 1</math> | The following algorithm gives us an r-ruling set with <math>r=2*\log n - 1</math> | ||
# Apply the deterministic coin tossing algorithm to give each element a tag in <math>[0,...,2*\log n - 1]</math> | |||
# For each element i in parallel, if i is a local maximum then add it to <math>S</math> | |||
==Tree Contraction== | ==Tree Contraction== | ||