On Cluster Editing Problem with Clusters of Small Sizes Научная публикация
| Конференция |
XIV International Conference Optimization and Applications 18-22 сент. 2023 , Петровац, Черногория |
||||||
|---|---|---|---|---|---|---|---|
| Сборник | Optimization and Applications : 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers Сборник, Springer. 2023. 390 c. ISBN 9783031478598. |
||||||
| Журнал |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||||||
| Вых. Данные | Год: 2023, Том: 14395, Страницы: 316-328 Страниц : 13 DOI: 10.1007/978-3-031-47859-8_23 | ||||||
| Ключевые слова | Cluster editing · Approximation algorithm · Performance guarantee | ||||||
| Авторы |
|
||||||
| Организации |
|
Информация о финансировании (2)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Реферат:
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 =3 and s =4, respectively. We also show that the cluster editing problem is APX-complete for the case s =3even if the maximum degree of the graphs is bounded by 4.
Библиографическая ссылка:
Kononov A.
, Il’ev V.
On Cluster Editing Problem with Clusters of Small Sizes
В сборнике Optimization and Applications : 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers. – Springer., 2023. – C.316-328. – ISBN 9783031478598. DOI: 10.1007/978-3-031-47859-8_23 Scopus OpenAlex
On Cluster Editing Problem with Clusters of Small Sizes
В сборнике Optimization and Applications : 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers. – Springer., 2023. – C.316-328. – ISBN 9783031478598. DOI: 10.1007/978-3-031-47859-8_23 Scopus OpenAlex
Даты:
| Опубликована в печати: | 10 нояб. 2023 г. |
| Опубликована online: | 10 нояб. 2023 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85177175477 |
| OpenAlex: | W4388522890 |