Literature review Comparatives Analysis

Chapter Two
Literature review
2.1 Introduction
Compared the performance of Prim and Kruskal’s algorithm on the Shanghai and Shenzhen 300 index daily stock exchange data between 2005 and 2007, that is, they compared the performance of both MST algorithms in constructing the super metric space of the sample stocks within this period. Comparison of the space complexity of both algorithms showed that Kruskal’s algorithm was superior with an input data less than 100, whereas the time complexity of prims algorithm was superior to Kruskal’s with an input data size greater than 100 but had little difference when a data size less than 100 was used. [Fallin et al. (2023)] designed an optimal route for the water supply system in the Kwahu South District of Ghana using Prim's algorithm. The map used consisted of 12 nodes and the distances between the towns were the weights of the graph. It was seen from the results that the total cost of pipeline construction was significantly reduced when the MST was used. W. B., Ram, P., [2010] also applied the Prims algorithm in designing an optimized LAN network for Chuka University, Kenya. The algorithm was used to determine the shortest length of cables to directly link a set of network nodes supposing all buildings in the university are connected. The graph used consisted of 11 nodes and the distance between the buildings were the weights of the graph. The result showed that the Prims algorithm produced a route with minimal distance and therefore optimizes the installation cost of the optic fiber in the LAN network Schimek, M. (2023). also studied the use of MSTs based on optimization of time and cost for temporal graphs. The MST based on cost optimization for temporal graphs was treated as a Directed Steiner tree problem, that is, it was transformed into a static graph. Then, a lineartime algorithm for finding the optimal cost MST was introduced. Prim’s algorithm for minimum spanning tree has been used by [Alves and Garg (2022)] in the transportation system of the Odeda local government in Nigeria. The graph used consisted of 88 nodes and 96 paths where the nodes and paths represent the villages and the connecting roads. It was concluded that Prim’s algorithm proved effective in providing the shortest routes and in reducing the fuel cost for transportation in that LGA. Also, Alves and Garg (2022) performed a similar implementation but made use of Prim’s algorithm in producing the minimum spanning tree of the 36 state capitals in Nigeria with Yenagoa as the starting node. They proposed the construction of the optimal road network discovered, in the design of telecommunication networks, transportation and even petroleum pipelines. Also, [Alves, D. R., 2023] proposed the use of neutrosophic numbers instead of a real/fuzzy number as weights on the graph in generating the minimal spanning tree. The proposed algorithm is a modification of Kruskal’s algorithm and produces both the cost and MST of a neutrosophic graph. The algorithm was compared with existing algorithms and it was shown that the proposed scheme was simple and efficient and suitable for realworld supply chain and transportation problems. [Alves, D. R., 2022] developed a heuristic algorithm that combines reinforcement learning and graph embedding in solving optimization problems. The algorithm proposed, incrementally constructs a minimal spanning tree solution, acting like a greedy metaalgorithm. The deep learning architecture used, Structure2vec deep Q-learning, was shown to be efficient and effective in learning greedy heuristics. Thus, the proposed method catered for difficulties that occur when applying conventional MST algorithms on large data sets.
Minimum spanning tree (MST) algorithms such as Kruskal’s, Prim’s, and Borůvka’s have well-understood theoretical properties but differ in practical performance and applications. Their worst-case time complexities are comparable (near-O(m log n) for a graph with n vertices and m edges), but constant factors and data structures vary. For example, Kruskal’s algorithm sorts all edges and runs in $O(m\log n)$ time, while Prim’s algorithm (with a Fibonacci heap) runs in $O(m + n\log n)$ timemlpack.org. Borůvka’s algorithm repeatedly connects each component by its lightest outgoing edge, taking $O(\log n)$ rounds and $O(m\log n)$ total timemlpack.org. In practice all three run in roughly linear ($O(m\log n)$) time on typical inputs, but advanced algorithms achieve near-linear bounds: for instance, Chazelle’s and Pettie–Ramachandran’s algorithms solve MST in $O(m \alpha(m,n))$ time (where $\alpha$ is the inverse Ackermann function)mlpack.org. Space usage is also linear ($O(m+n)$) for all three: Prim’s needs $O(n)$ space for the priority queue, Kruskal’s uses $O(m)$ for edge storage and $O(n)$ for a union-find, and Borůvka’s uses similar structures.
• Prim’s algorithm: Maintains a priority queue of vertices. Worst-case time $O(m + n\log n)$mlpack.org, space $O(n+m)$.
• Kruskal’s algorithm: Sorts edges and uses union-find. Worst-case $O(m\log n)$mlpack.org, space $O(n+m)$.
• Borůvka’s algorithm: Runs in at most $\lceil\log n\rceil$ rounds, each scanning edges, total $O(m\log n)$mlpack.org, space $O(n+m)$.
Modern theory shows these can be improved to nearly linear time. In fact, Pettie and Ramachandran (2002) achieved an $O(m\alpha(m,n))$ MST algorithmmlpack.org, indicating that in practice MST can often be found almost as fast as the time to read the input graph.
2.2 Practical Performance
In empirical tests, Prim vs. Kruskal vs. Borůvka each has regimes of advantage. Kruskal’s tends to excel on sparse graphs because sorting fewer edges is cheaper, whereas Prim’s algorithm (especially its simple $O(n^2)$ dense implementation) often wins on dense graphs when $m\approx n^2$mlpack.org. Borůvka’s original form is not commonly used serially, but its parallel nature makes it attractive for large-scale graphs. Recent GPU-based and parallel implementations blur these lines: for example, Fallin et al. (2023) show that a “filter-Kruskal” approach can handle both sparse and dense graphs efficiently by only partially sorting edgesuserweb.cs.txstate.edu. In their ECL-MST GPU implementation, Kruskal-based and Borůvka-based strategies yield the same high performance, with optimizations like edge filtering and lock-free data structures boosting both sparse and dense performanceuserweb.cs.txstate.eduuserweb.cs.txstate.edu.
• Sparse graphs (small m): Kruskal’s method with efficient sorting or filtering often wins, because there are few edges to processuserweb.cs.txstate.edu.
• Dense graphs (large m): Prim’s algorithm using an adjacency-matrix or optimized heap (with time $O(n^2)$ or $O(m + n\log n)$) can be faster than sorting $\Theta(n^2)$ edges. Advanced Kruskal variants (like Filter-Kruskal) can also match this performanceuserweb.cs.txstate.edu.
• Mixed/large graphs: Hybrid implementations (e.g. parallel Borůvka or Filter-Borůvka) show best scaling. For example, an MPI-based Borůvka algorithm achieved 800× speedup on a 65K-core clusterarxiv.org, far outpacing standard serial implementations on very large graphs.
Memory and space overheads are similar for all: each algorithm needs space proportional to the graph size plus auxiliary structures (heaps or union-find). In high-performance settings, memory access patterns and parallel overhead often dominate. For instance, GPU implementations must minimize synchronization and redundant work; ECL-MST avoids full sorting to reduce memory trafficuserweb.cs.txstate.edu.
2.3 Application Contexts
Minimum spanning trees arise in diverse domains. Prominent applications include:
• Network design: Building cost-minimal communication or transportation networks is a classic use of MSTs. For example, designing minimal cable layouts or broadcast trees often directly uses MSTsarxiv.org.
• Clustering and Data Analysis: Hierarchical clustering (single-linkage) is equivalent to cutting a graph’s MST, and MSTs are used for clustering spatial or high-dimensional data. In particular, image segmentation algorithms (e.g. Felzenszwalb–Huttenlocher) create a graph of pixels and find an MST to identify regions. Modern over-segmentation methods and computer-vision tasks continue to use MST techniquesarxiv.org.
• Connectivity and Infrastructure: MSTs model minimal connections in power grids, road networks, and wireless sensor networks. For example, connecting distributed sensors with minimal total wiring uses MST computations, and efficient MST algorithms are key in geographic and telecommunication planningarxiv.org.
Other areas include approximating the traveling-salesman path, morphological skeletons in image processing, and clustering in machine learning. In all these contexts, algorithm choice depends on graph characteristics: large-scale networks favor parallel Borůvka-based solvers, while moderate-sized dense problems may use optimized Prim variants.
2.4 Adaptations and Optimizations
Recent research has produced many parallel, distributed, and specialized versions of MST algorithms:
• Shared-memory parallel algorithms: Alves and Garg (2022) introduced LLP-Prim and LLP-Borůvka, formulations based on lattice-linear predicates. Their LLP-Prim reduces priority-queue operations by enabling edge selections without heap updates, and their LLP-Borůvka minimizes synchronization. In practice, LLP-Prim outperforms a standard Prim’s in both single-threaded and multi-threaded runsusers.ece.utexas.edu. Likewise, others have parallelized Prim by having threads grow multiple trees and merge them (using cut properties)userweb.cs.txstate.edu. These methods scale well up to tens of CPU cores, with lock-free atomic operations eliminating contentionuserweb.cs.txstate.eduusers.ece.utexas.edu.

    Date: 2026-08-02 00:00:00.000000