Online Query Optimization Through an Effective Kruskal's Algorithm

Finding the MST of a weighted connected and undirected graph plays a vital role in different applications of the real world such as effective route finding during navigation, faster cellphone connectivity, timely message delivery, etc. In such a scenario Kruskal's algorithm can determine the optimal results and has gained major attention of researchers from the time it was first proposed. However, the algorithm suffers from complexity issues. Sometimes for a dense network with a large number of queries Kruskal's complexity proves to be the worst. In this paper, we tried to modify and reduce the complexity issue of the existing Kruskal algorithm. The proposed approach finds a spanning tree in the graph using a new batch-processing parallel algorithm. For justification, the proposed approach is compared with existing approaches for finding MST. The comparative result shows the effectiveness of the proposed approach on the basis of node time comparison and edge time comparison.