Parallel algorithms for graph theory problems

Parallel algorithms for graph theory problems
parallel_graph_algorithms.pdf (Size: 521.63 KB / Downloads: 64)
Sparse and dense graphs
A graph G(V,E) is sparse if E is match smaller than O(V2)
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 (VVT), 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] 

