**Post: #1**

Parallel algorithms for graph theory problems

parallel_graph_algorithms.pdf (Size: 521.63 KB / Downloads: 66)

Sparse and dense graphs

A graph G(V,E) is sparse if |E| is match smaller than O(|V|2)

Matrix representation is suitable for dense graphs and list representation

for sparse

Spanning Tree

A spanning tree of a graph G is a tree that contains all vertices of G

A minimum spanning tree (MST) for a weighted graph is a spanning tree with

minimum weight

Prim’s algorithm

Starts from an arbitrary vertex u

Repeat until all vertices are included:

Selects vertex v so that the edge (u,v) is in MST

Let A=(aij) be the matrix representation of G=(V,E,w)

Let VT be the set of vertices found to be in the MST

Let d[1..n] be a vector.

For each v (V-VT), d[v] holds the weight of the edge with the least

weight from any vertex in VT to v

In each iteration , a new v is chosen with the minimum d[v]