5,323
edits
Parallel Algorithms: Difference between revisions
→r-ruling set
| Line 492: | Line 492: | ||
*''Uniform Sparcity'' If node <math>i</math> is in <math>S</math> then node <math>next(i)</math> is not in <math>S</math> | *''Uniform Sparcity'' If node <math>i</math> is in <math>S</math> then node <math>next(i)</math> is not in <math>S</math> | ||
;Algorithm | ;Algorithm 1 | ||
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> | ||
| Line 498: | Line 498: | ||
#Apply the deterministic coin tossing algorithm to give each element a tag in <math>[0,...,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> | #For each element i in parallel, if i is a local maximum then add it to <math>S</math> | ||
;Optimal-Work 2-Ruling set | |||
<pre> | |||
Apply one iteration of deterministic coin tossing | |||
Sort elements by tags | |||
Initialize array S with 1s | |||
for k = 0 to 2*log(n)-1: | |||
for i such that tag(i) = k pardo | |||
if S(pre(i)) = S(next(i)) = 1: | |||
S(i) = 0 | |||
</pre> | |||
==Tree Contraction== | ==Tree Contraction== | ||