On Cluster Editing Problem with Clusters of Small Sizes Full article
| Conference |
XIV International Conference Optimization and Applications 18-22 Sep 2023 , Петровац, Черногория |
||||||
|---|---|---|---|---|---|---|---|
| Source | Optimization and Applications : 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers Compilation, Springer. 2023. 390 c. ISBN 9783031478598. |
||||||
| Journal |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||||||
| Output data | Year: 2023, Volume: 14395, Pages: 316-328 Pages count : 13 DOI: 10.1007/978-3-031-47859-8_23 | ||||||
| Tags | Cluster editing · Approximation algorithm · Performance guarantee | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
| 2 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Abstract:
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.
Cite:
Kononov A.
, Il’ev V.
On Cluster Editing Problem with Clusters of Small Sizes
In compilation 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
In compilation 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
Dates:
| Published print: | Nov 10, 2023 |
| Published online: | Nov 10, 2023 |
Identifiers:
| Scopus: | 2-s2.0-85177175477 |
| OpenAlex: | W4388522890 |