EUVIMEDEUVIMED entdecken
Crossref

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

Artem Viktorovich Ilev

Дискретная математика · 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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →