5,323
edits
Parallel Algorithms: Difference between revisions
→Tree Contraction
| Line 550: | Line 550: | ||
The internal node will be <math>(a*l+b) \times (c*r+d)</math> where <math>\times</math> is either addition or multiplication.<br> | The internal node will be <math>(a*l+b) \times (c*r+d)</math> where <math>\times</math> is either addition or multiplication.<br> | ||
If we delete one leaf and it's parent (stem), we will modify these variables of the stem's parent. | If we delete one leaf and it's parent (stem), we will modify these variables of the stem's parent. | ||
===Tree Binarization=== | |||
;Note: This is not in the classnotes, but has been covered in exams. | |||
To apply the above techniques to general trees or k-ary trees, you should binarize your k-ary tree.<br> | |||
This is done as follows: | |||
* Suppose node <math>x</math> has <math>n > 2</math> children | |||
* Select one child to keep | |||
* Create a node <math>x'</math> | |||
* Move all <math>n-1</math> children to <math>x'</math> | |||
* Set child <math>x'</math> to be a child of <math>x</math> | |||
==Graph Connectivity== | ==Graph Connectivity== | ||