Влияние выбора алгоритма разбиения графа на производительность параллельной программы

Abstract

В общем случае постановка задачи поиска минимального разбиения (иногда употребляется термин «минимальный разрез») графа формулируется следующим образом. Пусть дан неориентированный граф G = (V, E), где V – множество его вершин, G – множество его ребер. Необходимо разделить множество V на k непересекающихся подмножеств таким образом, чтобы каждое из этих подмножеств имело приблизительно одинаковую мощность, но количество ребер, соединяющих вершины из разных подмножеств должно быть минимальным. Отметим, что эта задача имеет важное практическое применение в области параллельных вычислений для разбиения задач на подзадачи.