Clustering Complexity and an Approximation Algorithm for a Version of the Cluster Editing Problem Научная публикация
| Конференция |
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 июн. - 6 июл. 2024 , Омск |
||||
|---|---|---|---|---|---|
| Сборник | Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings Сборник, Springer Cham. Switzerland.2024. 464 c. ISBN 978-3-031-62792-7. |
||||
| Журнал |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||||
| Вых. Данные | Год: 2024, Том: 14766, Страницы: 103-115 Страниц : 13 DOI: 10.1007/978-3-031-62792-7_7 | ||||
| Ключевые слова | Graph cluster editing · Approximation algorithm · Performance guarantee · Clustering complexity | ||||
| Авторы |
|
||||
| Организации |
|
Информация о финансировании (2)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
| 2 | Российский научный фонд | 22-11-20019 |
Реферат:
In graph clustering problems, one has to partition the vertex set of a given undirected graph into pairwise disjoint subsets (clusters). Vertices of the graph correspond to some objects, edges connect the pairs of similar objects. In cluster editing (CE) problems the goal is to find a nearest to a given graph G =(V,E) cluster graph, i.e., a graph on the same vertex set V each connected component of which is a complete graph. The distance between graphs is understood as the number of their non-coinciding edges. The distance between a graph G and a nearest to G cluster graph is called clustering complexity of G. We consider a version of CE problem in which the size of each cluster is bounded from above by a positive integer s. This problem is NP hard for any fixed s ⩾ 3. In 2015, Puleo and Milenkovic proposed a 6-approximation algorithm for this problem. For the version of the problem with s =5we propose a polynomial time approximation algorithm with better performance guarantee and prove an upper bound on clustering complexity of a graph that is better than earlier known one.
Библиографическая ссылка:
Il’ev A.
, Il’ev V.
Clustering Complexity and an Approximation Algorithm for a Version of the Cluster Editing Problem
В сборнике Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings. – Springer Cham., 2024. – C.103-115. – ISBN 978-3-031-62792-7. DOI: 10.1007/978-3-031-62792-7_7 Scopus OpenAlex
Clustering Complexity and an Approximation Algorithm for a Version of the Cluster Editing Problem
В сборнике Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings. – Springer Cham., 2024. – C.103-115. – ISBN 978-3-031-62792-7. DOI: 10.1007/978-3-031-62792-7_7 Scopus OpenAlex
Даты:
| Поступила в редакцию: | 20 февр. 2024 г. |
| Опубликована в печати: | 18 июн. 2024 г. |
| Опубликована online: | 18 июн. 2024 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85198437227 |
| OpenAlex: | W4399743146 |
Цитирование в БД:
Пока нет цитирований