Parallel implementation of the search algorithm for minimum spanning trees using central and graphic processors
Author
A.S. Kolganov
Annotation
The solution of the problem to search a minimum spanning trees is widespread in various fields of researches: recognition of different objects, computer vision, analysis and creation of networks (for example, telephone, electrical, computer, road, etc.), chemistry and biology and many others. There are at least three well-known algorithms that solve this problem: Boruvka’s, Kruskal’s and Prim’s. Large graph processing is a time-consuming task for Central processor unit (CPU) and is popular at present. The graphic accelerators (GPU) having greater computational power, than CPU, become more and more widespread for solution of general purpose tasks. But this problem, as well as many graph processing tasks, badly lays down on GPU architecture. In this article hybrid implementation of the algorithm will be considered.
Key words
MST, CUDA, NVidia, Graphs, Boruvka.
Language
Russian
Presented on
Reference
A.S. Kolganov. Parallel implementation of the search algorithm for minimum spanning trees using central and graphic processors // Proceedings of the international scientific conference "Parallel Computational Technologies (PCT'2016)", Chelyabinsk: Publishing center SUSU, 2016, P. 530-543