An Approximation Algorithm for Graph Clustering with Clusters of Bounded Sizes Full article
| Journal |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2022, Volume: 1661 CCIS, Pages: 68-75 Pages count : 8 DOI: 10.1007/978-3-031-16224-4_4 | ||||
| Tags | Approximation algorithm; Graph clustering; Performance guarantee | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Abstract:
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.
Cite:
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
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
Identifiers:
| Scopus: | 2-s2.0-85140451534 |
| OpenAlex: | W4312956446 |
Citing:
Пока нет цитирований