Краткие сообщения

Подход к разбиению сверхбольших графов с помощью параллельных СУБД

К. С. Пан

Южно-Уральский государственный университет (г. Челябинск, Российская Федерация)

Аннотация: Разбиение графов на подграфы представляет собой интересную задачу интеллектуального анализа графов, которая находит свое применение в ряде теоретических и практических задач (раскраска графа, проектирование БИС и ПЛИС, конечно-элементное моделирование и др.). Существующие последовательные и параллельные алгоритмы предполагают возможность размещения графов и промежуточных данных обработки в оперативной памяти и неприменимы для случая сверхбольших графов. Представлен подход к обработке сверхбольших графов на основе использования параллельной реляционной СУБД PargreSQL, разработанной на базе свободной СУБД PostgreSQL.

Ключевые слова: интеллектуальный анализ, разбиение графов, параллельные СУБД.

УДК: 004.65, 004.272, 519.174.1

Поступила в редакцию: 16.10.2012

DOI: 10.14529/cmse120211