Approximation algorithms for the cluster editing problem with small clusters | Sciact - Система учета научной деятельности ИМ СО РАН

Approximation algorithms for the cluster editing problem with small clusters Научная публикация

Журнал

Discrete Optimization
ISSN: 1572-5286

Вых. Данные

Год: 2025, Том: 57, Номер статьи : 100900, Страниц : 14 DOI: 10.1016/j.disopt.2025.100900

Ключевые слова

Cluster editing, Approximation algorithm, Performance guarantee

Авторы

Kononov Alexander ¹ , Il’ev Victor ^2,3

Организации

1	Sobolev Institute of Mathematics SB RAS
2	Sobolev Institute of Mathematics SB RAS
3	Dostoevsky Omsk State University

Информация о финансировании (2)

1	Институт математики им. С.Л. Соболева СО РАН	FWNF-2022-0019
2	Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН».	FWNF-2022-0020

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.

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

Поступила в редакцию:	4 дек. 2023 г.
Принята к публикации:	23 мая 2025 г.
Опубликована в печати:	13 июн. 2025 г.
Опубликована online:	13 июн. 2025 г.

Scopus:

2-s2.0-105007969232

Пока нет цитирований