Electrotechnical and Computer Engineering
Vol. 39 No. 06 (2024): Proceedings of Faculty of Technical Sciences
PARALLEL BREADTH-FIRST SEARCH GRAPH TRAVERSAL ON COMPUTER ARCHITECTURES WITH DISTRIBUTED AND SHARED MEMORY
Abstract
The main focus of this research paper is an attempt to improve upon graph traversal algorithms, especially in the cases of large graphs. This paper provides information about parallel graph traversal algorithms, as well as their implementation on distributed and parallel computer systems. Every type of implementation is analyzed through different parameters to test its achieved performance. The outcome of this research concluded that parallel graph traversal is performant in the case of computer architectures with shared memory, unfortunatelly only case where it becomes useful for architectures with distributed memory is when graph size becomes too large to fit on one node.
References
[1] D. A. Bader, Massive Graph Analytics, CRC Press, 2022.
[2] A. Yoo, E. Chow, K. Henderson, W. McLendon, U. Catalyurek i B. Hendrickson, A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L, ACM/IEEE Conference on Supercomputing, 2005.
[3] W. T. Tutte, Cambridge mathematical library: Graph theory, Cambridge: Cambridge University Press, 2001.
[4] K. Mehlhorn, Data structures and algorithms 2, Berlin: Springer, 2011.
[5] M. Neerajkumar, An efficient algorithm for shortest path tree in dynamic graph, LAP Lambert Academic Publishing, 2014.