Abstract:
Graphs are widely used in many
applications. Some of the applications that used
graph theory are: analysis of electrical circuits,
route planning, genetics, social sciences and so
on. The system is based on sequential algorithm of
Prim and will focus on its parallelization targeting
on message passing through the server and the
client. This system will introduce 2 strategies to
parallel the sequential Prim’s algorithm for
finding minimum spanning tree (MST) on clientserver
architecture. In the first strategy, the server
will compute the global minimum spanning tree by
asking the local minimum-weight edges of the
client every step of the computation. Server and
client follow every step of the Prim Algorithm and
exchange the messages back and forth until the
global minimum spanning tree is achieved. In the
later strategy, the server and client parallel
compute the local minimum spanning tree based
on their sub-graphs and then the client sends its
local minimum spanning tree to the server. The
server combines all local minimum spanning trees
and calculates a global one.
