Approximation algorithms for the cluster editing problem with small clusters Full article
| Journal |
Discrete Optimization
ISSN: 1572-5286 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2025, Volume: 57, Article number : 100900, Pages count : 14 DOI: 10.1016/j.disopt.2025.100900 | ||||||
| Tags | Cluster editing, Approximation algorithm, Performance guarantee | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Abstract:
Clustering is the task of dividing objects into groups (called clusters) so that objects in the same group are similar to each other. The Cluster Editing problem is one of the most natural ways to model clustering on graphs. In this problem, the similarity relation between objects is given by an undirected graph whose vertices correspond to the objects, edges connect couples of similar objects, and it is required to partition the set of vertices into disjoint subsets minimizing the number of edges between clusters and the number of missing edges within clusters. We present new approximation algorithms with better worst-case performance guarantees when cluster sizes are upper bounded by three or four vertices.
Cite:
Kononov A.
, Il’ev V.
Approximation algorithms for the cluster editing problem with small clusters
Discrete Optimization. 2025. V.57. 100900 :1-14. DOI: 10.1016/j.disopt.2025.100900 Scopus
Approximation algorithms for the cluster editing problem with small clusters
Discrete Optimization. 2025. V.57. 100900 :1-14. DOI: 10.1016/j.disopt.2025.100900 Scopus
Dates:
| Submitted: | Dec 4, 2023 |
| Accepted: | May 23, 2025 |
| Published print: | Jun 13, 2025 |
| Published online: | Jun 13, 2025 |
Identifiers:
| Scopus: | 2-s2.0-105007969232 |
Citing:
Пока нет цитирований