5,323
edits
Parallel Algorithms: Difference between revisions
→Tree Binarization
| Line 561: | Line 561: | ||
* Move all <math>n-1</math> children to <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> | * Set child <math>x'</math> to be a child of <math>x</math> | ||
Complexity | |||
* The time is <math>O(max\_degree)</math> and the work is <math>O(n)</math> | |||
==Graph Connectivity== | ==Graph Connectivity== | ||