Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера Научная публикация
| Журнал |
Дискретный анализ и исследование операций
ISSN: 1560-7542 |
||||||
|---|---|---|---|---|---|---|---|
| Вых. Данные | Год: 2024, Том: 31, Номер: 4, Страницы: 40–57 Страниц : 16 DOI: 10.33048/daio.2024.31.802 | ||||||
| Ключевые слова | граф, кластеризация, NP-трудная задача, приближённый алгоритм, гарантированная оценка точности. | ||||||
| Авторы |
|
||||||
| Организации |
|
Информация о финансировании (2)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Реферат:
В задачах кластеризации на графах требуется разбить множество вершин заданного графа на попарно непересекающиеся подмножества (называемые кластерами) так, чтобы минимизировать число рёбер между кластерами и число отсутствующих рёбер внутри кластеров. Мы рассматриваем вариант задачи, в котором размеры кластеров ограничены сверху натуральным числом s. Задача NP-трудна для любого фиксированного s 3. Для этого варианта задачи предложены полиномиальные приближённые алгоритмы с гарантированными оценками точности, равными 5/3 в случае s = 3 и 2 в случае s = 4. Доказано также, что при s = 3 задача APX-трудна. Ил. 5, библиогр. 20.
Библиографическая ссылка:
Ильев В.П.
, Ильева С.Д.
, Кононов А.В.
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802 РИНЦ OpenAlex
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802 РИНЦ OpenAlex
Переводная:
Il’ev V.P.
, Il’eva S.D.
, Kononov A.V.
Approximation Algorithms for Graph Clustering Problems with Clusters of Bounded Size
Journal of Applied and Industrial Mathematics. 2024. V.18. N4. P.686-696. DOI: 10.1134/s1990478924040069 Scopus РИНЦ OpenAlex
Approximation Algorithms for Graph Clustering Problems with Clusters of Bounded Size
Journal of Applied and Industrial Mathematics. 2024. V.18. N4. P.686-696. DOI: 10.1134/s1990478924040069 Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 17 мая 2024 г. |
| Принята к публикации: | 24 июн. 2024 г. |
| Опубликована в печати: | 30 дек. 2024 г. |
| Опубликована online: | 30 дек. 2024 г. |
Идентификаторы БД:
| РИНЦ: | 82606993 |
| OpenAlex: | W4414103261 |
Цитирование в БД:
Пока нет цитирований