A parallel algorithm for finding minimal spanning tree of big graphs

A parallel algorithm for finding minimal spanning tree of big graphs

In graph theory and applications, using the classical algorithms such as Kruskal for finding the minimum spanning tree is very usual and beneficial; but for very large graphs, they need too much time and perform inefficiently. In order to achieve the expected performance, in this paper we present an effective method, which relies on implementation of the relevant classical algorithms in parallel. In the proposed method, the problem space is divided into some subsets, and in each subset, according to some multi-thread calculations, the edges are arranged in a non-decreasing order. The obtained results are then combined with the parallel merge algorithm. Theoretical analyzes of the time order and the degree of computational complexity show that the proposed method can provide the expected performance.

In graph theory and applications, using the classical algorithms such as Kruskal for finding the minimum spanning tree is very usual and beneficial; but for very large graphs, they need too much time and perform inefficiently. In order to achieve the expected performance, in this paper we present an effective method, which relies on implementation of the relevant classical algorithms in parallel. In the proposed method, the problem space is divided into some subsets, and in each subset, according to some multi-thread calculations, the edges are arranged in a non-decreasing order. The obtained results are then combined with the parallel merge algorithm. Theoretical analyzes of the time order and the degree of computational complexity show that the proposed method can provide the expected performance.