Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров
Дискретная математика · 2026 · 38 (1) · 43-53
DOI: 10.4213/dm1913 ↗Kurz gefasst
Fachartikel in der Zeitschrift Дискретная математика, online erschienen am 01.03.2026. Verfasst von Artem Viktorovich Ilev. Die Arbeit nennt 13 Literaturangaben. Gefördert von: Russian Science Foundation.
Abstract (Originalsprache)
В работе рассматриваются две задачи кластеризации на графах: Cluster Editing (CE) и Cluster Deletion (CD), в которых размеры кластеров ограничены сверху числом $s \geqslant 4$. В задаче CE для заданного графа $G$ требуется найти ближайший к нему кластерный граф, а в задаче CD требуется найти ближайший к $G$ кластерный подграф на том же множестве вершин. Расстояние от графа $G$ до ближайшего кластерного графа называется сложностью кластеризации графа $G$. Получена верхняя оценка сложности кластеризации для задачи CD в случае произвольного $s$, которая также является лучшей известной верхней оценкой сложности кластеризации для задачи CE при $s>5$.
Förderung
- Russian Science Foundation
Zitieren
APA
Ilev, A. V. (2026). Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров. Дискретная математика, 38(1), 43-53. https://doi.org/10.4213/dm1913
Vancouver
Ilev AV. Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров. Дискретная математика. 2026;38(1):43-53. doi:10.4213/dm1913
BibTeX
@article{Ilev2026,
author = {Ilev, Artem Viktorovich},
title = {Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров},
journal = {Дискретная математика},
year = {2026},
volume = {38},
number = {1},
pages = {43--53},
doi = {10.4213/dm1913}
}
EUVIMED