Approximation Algorithms for Graph Clustering Problems with Clusters of Bounded Size Научная публикация
| Журнал |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||||||
|---|---|---|---|---|---|---|---|
| Вых. Данные | Год: 2024, Том: 18, Номер: 4, Страницы: 686-696 Страниц : 11 DOI: 10.1134/s1990478924040069 | ||||||
| Ключевые слова | Keywords: graph, clustering, NP-hard problem, approximation algorithm, performance guarantee | ||||||
| Авторы |
|
||||||
| Организации |
|
Информация о финансировании (2)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Реферат:
In the cluster editing problem, one has to partition the set of vertices of a graph into pairwise disjoint subsets (called clusters) minimizing the number of edges between clusters and the number of missing edges within clusters. We consider a version of the problem in which cluster sizes are bounded from above by a positive integer s. This problem is NP-hard for any fixed s ⩾ 3. We propose polynomial-time approximation algorithms for this version of the problem. Their performance guarantees equal 5/3 for the case s = 3 and 2 for s = 4. We also show that the cluster editing problem is APX-hard for the case of s = 3.
Библиографическая ссылка:
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
Оригинальная:
Ильев В.П.
, Ильева С.Д.
, Кононов А.В.
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802 РИНЦ
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802 РИНЦ
Даты:
| Поступила в редакцию: | 17 мая 2024 г. |
| Принята к публикации: | 22 июн. 2024 г. |
| Опубликована в печати: | 25 дек. 2024 г. |
| Опубликована online: | 11 июл. 2025 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-105010490395 |
| РИНЦ: | 82621655 |
| OpenAlex: | W4412194780 |
Цитирование в БД:
Пока нет цитирований