О сложности кластеризации графа в задаче с ограничениями на размеры кластеров

Балджанова, Роза Вагиф кызы; Ильев, Артем Викторович; Ильев, Виктор Петрович

О сложности кластеризации графа в задаче с ограничениями на размеры кластеров

Балджанова, Роза Вагиф кызы, Ильев, Артем Викторович, Ильев, Виктор Петрович

Дата публикации: 2023

Дата публикации в реестре: 2023-12-05T16:07:57Z

Аннотация:

В задачах кластеризации на графах для данного графа G требуется найти ближайший к нему кластерный граф на том же множестве вершин. Граф называется кластерным, если каждая его компонента связности является полным графом. Расстояние между двумя графами понимается как число несовпадающих рёбер. Рассматривается задача кластеризации на графах, в которой размеры кластеров ограничены сверху числом s. Доказана верхняя оценка сложности кластеризации произвольного графа для случая s = 2. Предложен приближённый полиномиальный алгоритм решения задачи кластеризации на графах для случая s = 3 и доказана верхняя оценка сложности кластеризации произвольного графа для этого случая.

Ключевые слова:
графы, кластеризация графов, сложность кластеризации

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2023. № 60. С. 76-84