5,323
edits
Parallel Algorithms: Difference between revisions
→Parallel Rake
| Line 464: | Line 464: | ||
;Parallel Rake Contraction Algorithm | ;Parallel Rake Contraction Algorithm | ||
Step 1 | ;Step 1 | ||
* Number leaves according to a DFS using the Euler tour algorithm.<br> | |||
Observation 3: | Observation 3: | ||
| Line 472: | Line 473: | ||
Proof: See the classnotes | Proof: See the classnotes | ||
Step 2: | ;Step 2: | ||
* Let <math>S_1</math> be nodes in <math>S</math> whose parents are not in <math>S</math>. | * Let <math>S_1</math> be nodes in <math>S</math> whose parents are not in <math>S</math>. | ||
; Let <math>L_1</math> be leaves in <math>L</math> whose parents are in <math>S_1</math>. | ; Let <math>L_1</math> be leaves in <math>L</math> whose parents are in <math>S_1</math>. | ||