Computing a spanning tree (ST) and a minimum ST (MST) of a graph are fundamental problems in graph theory and arise as a subproblem in many applications. In this article, we propose parallel algorithms to these problems. One of the steps of previous parallel MST algorithms relies on the heavy use of parallel list ranking which, though efficient in theory, is very time-consuming in practice. Using a different approach with a graph decomposition, we devised new parallel algorithms that do not make use of the list ranking procedure. We proved that our algorithms are correct, and for a graph , , and , the algorithms can be executed on a Bulk Synchronous Parallel/Coarse Grained Multicomputer (BSP/CGM) model using communications rounds with computation time for each round. To show that our algorithms have good performance on real parallel machines, we have implemented them on graphics processing unit. The obtained speedups are competitive and showed that the BSP/CGM model is suitable for designing general purpose parallel algorithms.
CáceresENDehneFMongelliH. (2003) A coarse-grained parallel algorithm for spanning tree and connected components. Technical Report RT-MAC-2003-06. São Paulo, Brazil: Department of Computer Science, Institute of Mathematics and Statistics, University of São Paulo.
2.
CáceresENDehneFMongelliH. (2004) A coarse-grained parallel algorithm for spanning tree and connected components. In: (eds MarcoDMarcoVDomenicoL) Proceedings of Euro-Par 2004. lecture notes in computer science. Berlin: Springer, vol. 3149, pp. 828–831.
3.
CáceresENDeoNSastryS. (1993) On finding Euler tours in parallel. Parallel Processing Letters3(3): 223–231.
4.
CáceresENMongelliHNishibeC. (2010) Experimental results of a coarse-grained parallel algorithm for spanning tree and connected components. In: 2010 International conference on high performance computing simulation. pp. 631–637. IEEE.
5.
DehneFFabriARau-ChaplinA (1996) Scalable parallel computational geometry for coarse grained multicomputers. International Journal on Computational Geometry and Applications6(3): 298–307.
6.
DehneFFerreiraACáceresE. (2002) Efficient parallel graph algorithms for coarse grained multicomputers and BSP. Algorithmica33(2): 183–200.
7.
GrahamRLHellP (1985) On the history of the minimum spanning tree problem. In: Annals of the history of computing, vol. 7. pp. 43–57. IEEE.
8.
HawickKALeistAPlayneD (2010) Parallel graph component labelling with GPUs and CUDA. Parallel Computing36(12): 655–678.
9.
HirschbergDSChandraAKSarwateDV (1979) Computing connected components on parallel computers. Comm ACM22(8): 461–464.
10.
JohnsonbaughRKalinM (1991) A graph generation software package. In: Proceedings of the twenty-second SIGCSE technical symposium on computer science education, vol. 23. pp. 151–154. New York, NY: ACM.
11.
KarpRMRamachandranV (1990) Handbook of Theoretical Computer Science. vol. A. Cambridge: The MIT Press.
12.
KozenD (1992) The Design and Analysis of Algorithms. Berlin: Springer.
13.
KruskalJB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society7(1): 48–50.
14.
LimaACDBrancoRGFerrazS. (2016) Solving the maximum subsequence sum and related problems using BSP/CGM model and multi-GPU CUDA. Journal of The Brazilian Computer Society (Online)22: 1–13.
15.
MamunARajasekaranS (2016) An efficient minimum spanning tree algorithm. In: 2016 IEEE symposium on computers and communication (ISCC), Piscataway, pp. 1047–1052. IEEE.
16.
ManoochehriSGoodarziBGoswamiD (2017) An efficient transaction-based GPU implementation of minimum spanning forest algorithm. In: 2017 International conference on high performance computing & simulation (HPCS), pp. 643–650. DOI: 10.1109/HPCS.2017.100. IEEE.
17.
MarešM (2008) The saga of minimum spanning trees. Computer Science Review2(3): 165–221.
18.
NasreRBurtscherMPingaliK (2013) Morph algorithms on GPUs. In: Proceedings of the 18th ACM SIGPLAN symposium on principles and practice of parallel programming, pp. 147–156. New York, NY: ACM.
19.
NobariSCaoTTKarrasP. (2012) Scalable parallel minimum spanning forest computation. In: Proceedings of the 17th ACM SIGPLAN symposium on principles and practice of parallel programming, pp. 205–214. New York, NY: ACM.
20.
OsipovVSandersPSinglerJ (2009) The Filter-Kruskal minimum spanning tree algorithm. In: Proceedings of the eleventh workshop on algorithm engineering and experiments (ALENEX). society for industrial and applied mathematics (SIAM), pp. 52–61. Philadelphia, USA: Society for Industrial and Applied Mathematics.
21.
PrimRC (1957) Shortest connection networks and some generalizations. Bell Labs Technical Journal36(6): 1389–1401.
22.
ReifJH (1985) Depth-first search is inherently sequential. Information Processing Letters20(5): 229–234.
23.
ValiantLG (1990) A bridging model for parallel computation. Commun ACM33(8): 103–111.
24.
VasconcellosJFdACáceresENMongelliH. (2017) A parallel algorithm for minimum spanning tree on GPU. In: 2017 International symposium on computer architecture and high performance computing workshops (SBAC-PADW), pp. 67–72. Campinas, Brazil: IEEE.
25.
VineetVHarishPPatidarS. (2009) Fast minimum spanning tree for large graphs on the GPU. In: Proceedings of the conference on high performance graphics 2009, HPG ‘09, pp. 167–171. New York, NY: ACM.
