The influence of Distributed BFS algorithms in reducing the computational complexity

Breadth-first search (BFS) is a cornerstone of algorithmic algorithms for complex graphs. In the worst case, BFS's linear complexity is determined by the number of edges and vertices, yet a recently discovered bottom-up method can reduce this complexity to the number of vertices in the best-case scenario, which is usually much less than the number of edges. The conventional top-down approach, however, always takes the same amount of time as the lowest case. To determine the direction, directional algorithms combine top-down and bottom-up methods, adapting between them as the boundary expands. Although bottom-up methods are not always the best option, their use in combination with top-down methods produces efficient algorithms. The main focus of this research is to improve search efficiency and reduce complexity by implementing a version of top-down algorithm optimisation. A scalable distributed-memory parallelisation technique is presented in this study, which has achieved speedups that are ten times faster than the previous purely toplevel approach. In previous studies, it has been demonstrated that this technique is superior to a 1D decomposition method.