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

doi:10.17223/20710410/45/7

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Алгоритмы приближенного решения одной задачи кластеризации графа	731 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/45/7

#графы

#кластеризация

#приближенные алгоритмы

#оценка точности решения

Title: Алгоритмы приближенного решения одной задачи кластеризации графа
Title: Approximate algorithms for graph clustering problem
Creator: Ильев, Виктор Петрович
|
Ильева, Светлана Диадоровна
|
Моршинин, Александр Владимирович
Date: 2019
DOI: 10.17223/20710410/45/7
Description: Изучается задача кластеризации графа. Для варианта задачи, в котором число кластеров не превосходит 3, разработаны три приближённых алгоритма. Первый алгоритм использует в качестве процедуры известный алгоритм Коулмана — Саундерсона — Вирта, который приближённо решает аналогичную задачу с числом кластеров, не превосходящим 2 , и многократно применяет локальный поиск. Второй алгоритм основан на оригинальной идее и вообще не использует локальный поиск. В третьем алгоритме процедура локального поиска применяется к допустимому решению, возвращенному вторым алгоритмом. Получены априорные гарантированные оценки точности всех трёх алгоритмов, лучшая из которых равна (6 — 12/n), где n — число вершин данного графа. Проведено также экспериментальное сравнение предложенных алгоритмов.