Approximation Algorithms for Graph Clustering Problems with Clusters of Bounded Size Full article
| Journal |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2024, Volume: 18, Number: 4, Pages: 686-696 Pages count : 11 DOI: 10.1134/s1990478924040069 | ||||||
| Tags | Keywords: graph, clustering, NP-hard problem, approximation algorithm, performance guarantee | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Abstract:
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.
Cite:
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
Original:
Ильев В.П.
, Ильева С.Д.
, Кононов А.В.
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802 РИНЦ
Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.40–57. DOI: 10.33048/daio.2024.31.802 РИНЦ
Dates:
| Submitted: | May 17, 2024 |
| Accepted: | Jun 22, 2024 |
| Published print: | Dec 25, 2024 |
| Published online: | Jul 11, 2025 |
Identifiers:
| Scopus: | 2-s2.0-105010490395 |
| Elibrary: | 82621655 |
| OpenAlex: | W4412194780 |
Citing:
Пока нет цитирований