An Approximation Algorithm for Graph Clustering with Clusters of Bounded Sizes | Sciact - Система учета научной деятельности ИМ СО РАН

An Approximation Algorithm for Graph Clustering with Clusters of Bounded Sizes Научная публикация

Журнал

Communications in Computer and Information Science
ISSN: 1865-0929

Вых. Данные

Год: 2022, Том: 1661 CCIS, Страницы: 68-75 Страниц : 8 DOI: 10.1007/978-3-031-16224-4_4

Ключевые слова

Approximation algorithm; Graph clustering; Performance guarantee

Авторы

Il’ev V. ^1,2 , Il’eva S. ¹ , Gorbunov N. ²

Организации

1	Dostoevsky Omsk State University, Omsk, Russian Federation
2	Sobolev Institute of Mathematics SB RAS, Omsk, Russian Federation

Информация о финансировании (1)

Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН».

FWNF-2022-0020

In graph clustering problems, 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 a polynomial-time approximation algorithm for this version of the problem. Its performance guarantee is better than earlier known bounds for all s⩾ 5. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Il’ev V. , Il’eva S. , Gorbunov N.
An Approximation Algorithm for Graph Clustering with Clusters of Bounded Sizes
Communications in Computer and Information Science. 2022. V.1661 CCIS. P.68-75. DOI: 10.1007/978-3-031-16224-4_4 Scopus OpenAlex

Scopus:	2-s2.0-85140451534
OpenAlex:	W4312956446

Пока нет цитирований