Четвертая Всероссийская научная конференция «Омские научные чтения - 2020» - Математика

О СЛОЖНОСТИ КЛАСТЕРИЗАЦИИ ГРАФОВ

Ильев В. П., Балджанова Р.

Аннотация

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

Комментарии

Комментарии отсутствуют

Вопросы по докладу

Вопросы отсутствуют