Реферат: In clustering problems, one has to partition a given set of objects into pairwise disjoint subsets (clusters) taking into account only similarity of objects. In the graph cluster editing problem similarity relation on the set of objects is given by an undirected graph whose vertices are in one-to-one correspondence with objects and edges correspond to pairs of similar objects. The goal is to find a nearest to a given graph G=(V,E)cluster graph, i.e., a graph on the vertex set V each connected component of which is a complete graph. The distance between graphs is understood as the Hamming distance between their incidence vectors. We consider a variant of the cluster editing problem in which the size of each cluster is bounded from above by a positive integer s. In 2011, Il’ev and Navrotskaya proved that this problem is NP-hard for any fixed s ⩾3. In 2015, Puleo and Milenkovic proposed a 6-approximation algorithm for this problem. In 2016, Il’ev, Il’eva and Navrotskaya presented an approximation algorithm that is 3-approximation in case of s =3 and 5-approximation in case of s =4. Now we propose simple greedy-type 2-approximation algorithms for these cases with tight performance guarantees.

Библиографическая ссылка: Il’ev V.P. , Il’eva S.
Approximation Algorithms for Graph Cluster Editing Problems with Cluster Size at Most 3 and 4
В сборнике Mathematical Optimization Theory and Operations Research: Recent Trends. – Springer., 2023. – Т.1881. – C.134-145. DOI: 10.1007/978-3-031-43257-6_11 Scopus OpenAlex

Даты:

Опубликована в печати:	21 сент. 2023 г.
Опубликована online:	21 сент. 2023 г.

Идентификаторы БД:

Scopus:	2-s2.0-85174564829
OpenAlex:	W4386891736

Цитирование в БД:

БД	Цитирований
OpenAlex	1
Scopus	1

Альметрики: