Алгоритмы приближенного решения одной задачи кластеризации графа В. П. Ильев, С. Д. Ильева, А. В. Моршинин
Material type:
ArticleOther title: Approximate algorithms for graph clustering problem [Parallel title]Subject(s): графы | кластеризация | приближенные алгоритмы | оценка точности решенияGenre/Form: статьи в журналах Online resources: Click here to access online
In:
Прикладная дискретная математика № 45. С. 64-77Abstract: Изучается задача кластеризации графа. Для варианта задачи, в котором число кластеров не превосходит 3, разработаны три приближённых алгоритма. Первый алгоритм использует в качестве процедуры известный алгоритм Коулмана — Саундерсона — Вирта, который приближённо решает аналогичную задачу с числом кластеров, не превосходящим 2 , и многократно применяет локальный поиск. Второй алгоритм основан на оригинальной идее и вообще не использует локальный поиск. В третьем алгоритме процедура локального поиска применяется к допустимому решению, возвращенному вторым алгоритмом. Получены априорные гарантированные оценки точности всех трёх алгоритмов, лучшая из которых равна (6 — 12/n), где n — число вершин данного графа. Проведено также экспериментальное сравнение предложенных алгоритмов.
Библиогр.: 16 назв.
Изучается задача кластеризации графа. Для варианта задачи, в котором число кластеров не превосходит 3, разработаны три приближённых алгоритма. Первый алгоритм использует в качестве процедуры известный алгоритм Коулмана — Саундерсона — Вирта, который приближённо решает аналогичную задачу с числом кластеров, не превосходящим 2 , и многократно применяет локальный поиск. Второй алгоритм основан на оригинальной идее и вообще не использует локальный поиск. В третьем алгоритме процедура локального поиска применяется к допустимому решению, возвращенному вторым алгоритмом. Получены априорные гарантированные оценки точности всех трёх алгоритмов, лучшая из которых равна (6 — 12/n), где n — число вершин данного графа. Проведено также экспериментальное сравнение предложенных алгоритмов.
There are no comments on this title.