|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
On Cluster Editing Problem with Clusters of Small Sizesтезисы доклада
- Авторы: Kononov A., Il’ev V.
- Сборник: Optimization and Applications: 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers
- Серия: Lecture Notes in Computer Science
- Том: 14395
- Тезисы
- Год издания: 2023
- Издательство: Springer-Verlag
- Местоположение издательства: Heidelberg, Germany
- Первая страница: 316
- Последняя страница: 328
- DOI: 10.1007/978-3-031-47859-8_23
- Аннотация: In the cluster editing problem, one has to partition the set of vertices of a graph into 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 are equal to 5/3 and 5/2 for the cases s = 3and s = 4, respectively.We also show that the cluster editing problem is APX-complete for the case s=3 even if the maximum degree of the graphs is bounded by 4.
- Добавил в систему: Кононов Александр Вениаминович