5,323
edits
Parallel Algorithms: Difference between revisions
→Tree Contraction
| Line 491: | Line 491: | ||
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. | ||
==Graph Connectivity== | |||
===Preliminaries=== | |||
For parallel algorithms, a graph can be represented as an incidence list or an adjacency matrix. | |||
An incidence list is an array of edges ordered by the starting point and ending point. | |||
An array of vertices point to the starting index of the vertices outgoing edges within the edge array. | |||
I.e. edges with index [v[i], v[i+1]) start at vertex i | |||
Definitions: | |||
* Pointer Graph | |||
* Supervertices | |||
* The supervertex graph | |||
* Hookings | |||
* Parallel pointer jumping | |||
===A first connectivity algorithm=== | |||
The first connectivity algorithm consists of <math>\log(n)</math> iterations of the following two steps: | |||
* Hookings - Each root hooks itself the the minimal adjacent root | |||
* Parallel pointer jumping - Each vertex performs pointer jumping until every vertex points to the root, forming a rooted star. | |||
;Complexity | |||
* We need <math>O(\log n)</math> iterations | |||
** Hookings take <math>O(1)</math> time and <math>O(n+m)</math> work | |||
** Pointer jumping takes <math>O(\log n)</math> time and <math>O(n\log n)</math> work | |||
* For adjacency matrix, in total we need <math>O(\log^2 n)</math> time and <math>O(n^2\log n)</math> work since we have a processor per <math>n^2</math> possible edges. | |||
* For incidence lists, we need <math>O(\log^2 n)</math> time and <math>O(n\log^2 n + m\log n)</math> work since we have a processor per edge. | |||
===A second connectivity algorithm=== | |||
===Minimum Spanning Forest=== | |||
==Resources== | ==Resources== | ||