Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров Full article
| Journal |
Дискретная математика
ISSN: 0234-0860 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2026, Volume: 38, Number: 1, Pages: 43-53 Pages count : 11 DOI: 10.4213/dm1913 | ||||
| Tags | граф, кластеризация, сложность кластеризации. | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 25-11-20023 |
Abstract:
В работе рассматриваются две задачи кластеризации на графах: Cluster Editing (CE) и Cluster Deletion (CD), в которых размеры кластеров ограничены сверху числом s⩾4. В задаче CE для заданного графа G требуется найти ближайший к нему кластерный граф, а в задаче CD требуется найти ближайший к G кластерный подграф на том же множестве вершин. Расстояние от графа G до ближайшего кластерного графа называется сложностью кластеризации графа G. Получена верхняя оценка сложности кластеризации для задачи CD в случае произвольного s, которая также является лучшей известной верхней оценкой сложности кластеризации для задачи CE при
s>5.
Cite:
Ilev A.V.
Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров
Дискретная математика. 2026. Т.38. №1. С.43-53. DOI: 10.4213/dm1913 OpenAlex
Оценка сложности кластеризации графа в задачах Cluster Deletion и Cluster Editing с ограничениями на размеры кластеров
Дискретная математика. 2026. Т.38. №1. С.43-53. DOI: 10.4213/dm1913 OpenAlex
Dates:
| Submitted: | Feb 14, 2025 |
| Published print: | Mar 1, 2026 |
| Published online: | Mar 1, 2026 |
Identifiers:
| ≡ OpenAlex: | W7133121092 |