Головков Александр Александрович

С. 156-169

С. 271-287

В данной статье с целью увеличения быстродействия алгоритмов решения графовых задач выполнен анализ структур данных, используемых для представления графов в машинной памяти, и предложена структура, ориентированная на параллельные вычислительные системы. Описаны необходимые свойства такой структуры. Оценена ее емкостная сложность, выявлены достоинства и недостатки. Приведена реализация параллельного алгоритма операции добавления вершины в граф на основе предложенной структуры на графическом процессоре CUDA. Выполнено сравнение времен работы последовательного и параллельного алгоритмов рассматриваемой операции. Экспериментальные данные позволили сделать вывод об эффективности применения параллельных операций с использованием предлагаемой структуры данных для представления графов, ориентированной на параллельные вычислительные системы.

С. 535-554

В данной статье с целью увеличения быстродействия алгоритмов решения графовых задач выполнен анализ существующих структур данных, используемых для представления графов в машинной памяти, и предложена структура, ориентированная на параллельные вычислительные системы. Описаны необходимые свойства такой структуры. Оценена ее емкостная сложность, выявлены достоинства и недостатки. Определены дальнейшие направления исследований в области разработки параллельных алгоритмов операций над графами на основе предложенной структуры данных.