Алгоритмы разбиения графов на GPU
Автор: Герб А.Р., Омарова Г.А.
Журнал: Проблемы информатики @problem-info
Рубрика: Прикладные информационные технологии
Статья в выпуске: 4 (61), 2023 года.
Бесплатный доступ
В данной работе рассматриваются два модифицированных и реализованных на GPU алгоритма: алгоритм меток и алгоритм Ja-Bc-Ja. Проведен сравнительный анализ работы на больших графах.
Граф, разреженная матрица, итерации, минимальный разрез
Короткий адрес: https://sciup.org/143182562
IDR: 143182562 | DOI: 10.24412/2073-0667-2023-4-78-87
Список литературы Алгоритмы разбиения графов на GPU
- CUDA С Programming Guide 7.5. ed: NVIDIA Corporation, 2016.
- 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. https: //, 2011. DOI: 10.1145/2049662.2049663
- Meyerhenke H., Monien B., Schamberger S. Graph partitioning and disturbed diffusion Parallel Computing. 2009. V. 35, iss. 10-11. P. 544-569. EDN: IXMPWN
- Gottesbiiren L. et al. Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022. 2021.
- 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.
- 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.
- 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.
- 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.
Статья научная
