Parallel Algorithms: Difference between revisions
| Line 461: | Line 461: | ||
;Parallel Rake Contraction Scheme | ;Parallel Rake Contraction Scheme | ||
Apply legal parallel rakes until the tree becomes a 3-node binary tree | Apply legal parallel rakes until the tree becomes a 3-node binary tree | ||
;Parallel Rake Contraction Algorithm | |||
Step 1: Number nodes according to a DFS using the Euler tour algorithm.<br> | Step 1: Number nodes according to a DFS using the Euler tour algorithm.<br> | ||
| Line 475: | Line 477: | ||
* Apply parallel rakes to leaves in <math>L_1</math>, unless the parent is the root. | * Apply parallel rakes to leaves in <math>L_1</math>, unless the parent is the root. | ||
* Apply parallel rakes to leaves in <math>L - L_1</math>, unless the parent is the root. | * Apply parallel rakes to leaves in <math>L - L_1</math>, unless the parent is the root. | ||
* Repeat Step 2 until the tree is a 3-node binary tree | |||
===Complexity=== | |||
Step 2 takes <math>O(\log n)</math> rounds. Each leaf gets raked only once.<br> | |||
In total we take <math>O(\log n)</math> time and <math>O(n)</math> work. | |||
==Resources== | ==Resources== | ||