Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров
Abstract
В работе рассматриваются две задачи кластеризации на графах: Cluster Editing (CE) и Cluster Deletion (CD), в которых размеры кластеров ограничены сверху числом $s \geqslant 4$. В задаче CE для заданного графа $G$ требуется найти ближайший к нему кластерный граф, а в задаче CD требуется найти ближайший к $G$ кластерный подграф на том же множестве вершин. Расстояние от графа $G$ до ближайшего кластерного графа называется сложностью кластеризации графа $G$. Получена верхняя оценка сложности кластеризации для задачи CD в случае произвольного $s$, которая также является лучшей известной верхней оценкой сложности кластеризации для задачи CE при $s>5$.
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Graph Labeling and Dimension Problems
Publication details
- Journal / source
- Дискретная математика
- Volume
- 38
- Issue
- 1
- Pages
- 43–53
- Publication date
- 1 January 2026
- Language
- RU