Алгоритмы приближённого решения одной задачи кластеризации графа

Изучается задача кластеризации графа. Для варианта задачи, в котором число кластеров не превосходит $3$, разработаны три приближённых алгоритма. Первый алгоритм использует в качестве процедуры известный алгоритм Коулмана–Саундерсона–Вирта, который приближённо решает аналогичную задачу с числом кластеров, не превосходящим $2$, и многократно применяет локальный поиск. Второй алгоритм основан на оригинальной идее и вообще не использует локальный поиск. В третьем алгоритме процедура локального поиска применяется к допустимому решению, возвращенному вторым алгоритмом. Получены априорные гарантированные оценки точности всех трёх алгоритмов, лучшая из которых равна ($6-12/n$), где $n$ — число вершин данного графа. Проведено также экспериментальное сравнение предложенных алгоритмов.