Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров | Sciact - Система учета научной деятельности ИМ СО РАН

Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров Научная публикация

Журнал

Дискретная математика
ISSN: 0234-0860

Вых. Данные

Год: 2026, Том: 38, Номер: 1, Страницы: 43-53 Страниц : 11 DOI: 10.4213/dm1913

Ключевые слова

граф, кластеризация, сложность кластеризации.

Авторы

Ilev Artem Viktorovich ^1,2

Организации

1	Caucasus Mathematical Center, Adyghe State University, Maikop
2	Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Информация о финансировании (1)

Российский научный фонд

25-11-20023

В работе рассматриваются две задачи кластеризации на графах: Cluster Editing (CE) и Cluster Deletion (CD), в которых размеры кластеров ограничены сверху числом s⩾4. В задаче CE для заданного графа G требуется найти ближайший к нему кластерный граф, а в задаче CD требуется найти ближайший к G кластерный подграф на том же множестве вершин. Расстояние от графа G до ближайшего кластерного графа называется сложностью кластеризации графа G. Получена верхняя оценка сложности кластеризации для задачи CD в случае произвольного s, которая также является лучшей известной верхней оценкой сложности кластеризации для задачи CE при s>5.

Ilev A.V.
Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров
Дискретная математика. 2026. Т.38. №1. С.43-53. DOI: 10.4213/dm1913 OpenAlex

Поступила в редакцию:	14 февр. 2025 г.
Опубликована в печати:	1 мар. 2026 г.
Опубликована online:	1 мар. 2026 г.

≡ OpenAlex:

W7133121092