АЛГОРИТМЫ РАЗБИЕНИЯ ГРАФОВ НА GPU

В данной работе рассматриваются два модифицированных и реализованных на GPU алгоритма: алгоритм меток и алгоритм Ja-Be-Ja. Проведен сравнительный анализ работы на больших графах.

Работа выполнена при финансовой поддержке Министерства пауки и высшего образования Российской Федерации (код проекта: 0251-2022-0001).

Список литературы

1.           CUDA С Programming Guide 7.5. ed: NVIDIA Corporation, 2016.

2.           Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software 38, 1, Article 1 (December 2011), 25 pages. DOI: https://doi.org/10.1145/2049662.2049663, 2011.

3.           Meyerhenke H., Monien B., Schamberger S. Graph partitioning and disturbed diffusion Parallel Computing. 2009. V. 35, iss. 10-11. P. 544-569.

4.           Gottesburen L. et al. Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022. 2021.

5.           Kumar R., Charpiat G., Thonnat M. Multiple object tracking by efficient graph partitioning // Computer Vision-ACCV 2014: 12th Asian Conference on Computer Vision, Singapore (Singapore), Nov. 1-5, 2014. Revised Selected Papers, Part IV 12. Springer International Publishing, 2015.

6.           Subelj L., Bajec M. Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction // Physical Review E. 2011. V. 83, iss. 3.

7.           Raghavan U. N., Albert R., Kumara S. Near linear time algorithm to detect community structures in large-scale networks // Physical review E. 2007. V. 52, No 3.

8.           Rahimian F., et al. Ja-be-ja: A distributed algorithm for balanced graph partitioning // IEEE 7th International Conference on Self-Adaptive and Self-Organizing Systems. IEEE, 2013. (с) А. Р. Герб, Г. А. Омарова, 2023