О сложности кластеризации графа в задаче с ограничениями на размеры кластеров Научная публикация
| Журнал |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||||
|---|---|---|---|---|---|
| Вых. Данные | Год: 2023, Номер: 60, Страницы: 76-84 Страниц : 9 DOI: 10.17223/20710410/60/6 | ||||
| Ключевые слова | граф, кластеризация, сложность кластеризации | ||||
| Авторы |
|
||||
| Организации |
|
Информация о финансировании (1)
| 1 | Российский научный фонд | 22-11-20019 |
Реферат:
В задачах кластеризации на графах для данного графа G требуется найти ближайший к нему кластерный граф на том же множестве вершин. Граф называется кластерным, если каждая его компонента связности является полным графом. Расстояние между двумя графами понимается как число несовпадающих рёбер. Рассматривается задача кластеризации на графах, в которой размеры кластеров ограничены сверху числом s. Доказана верхняя оценка сложности кластеризации произвольного графа для случая s = 2. Предложен приближённый полиномиальный алгоритм решения задачи кластеризации на графах для случая s = 3 и доказана верхняя оценка сложности кластеризации произвольного графа для этого случая.
Библиографическая ссылка:
Балджанова Р.В.
, Ильев А.В.
, Ильев В.П.
О сложности кластеризации графа в задаче с ограничениями на размеры кластеров
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. №60. С.76-84. DOI: 10.17223/20710410/60/6 WOS Scopus РИНЦ OpenAlex
О сложности кластеризации графа в задаче с ограничениями на размеры кластеров
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. №60. С.76-84. DOI: 10.17223/20710410/60/6 WOS Scopus РИНЦ OpenAlex
Даты:
| Опубликована в печати: | 19 июн. 2023 г. |
| Опубликована online: | 19 июн. 2023 г. |
Идентификаторы БД:
| Web of science: | WOS:001065160100006 |
| Scopus: | 2-s2.0-85177188598 |
| РИНЦ: | 53971748 |
| OpenAlex: | W4405724432 |