|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Approximation algorithms for the cluster editing problem with small clustersстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Kononov Alexander, Il’ev Victor
- Журнал: Discrete Optimization
- Том: 57
- Год издания: 2025
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Номер статьи: 100900
- DOI: 10.1016/j.disopt.2025.100900
- Аннотация: 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.
- Добавил в систему: Кононов Александр Вениаминович