Clustering Complexity and an Approximation Algorithm for a Version of the Cluster Editing Problem Full article
| Conference |
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 Jun - 6 Jul 2024 , Омск |
||||
|---|---|---|---|---|---|
| Source | Mathematical Optimization Theory and Operations Research : 23rd International Conference, MOTOR 2024, Omsk, Russia, June 30–July 6, 2024, Proceedings Compilation, Springer Cham. Switzerland.2024. 464 c. ISBN 978-3-031-62792-7. |
||||
| Journal |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||||
| Output data | Year: 2024, Volume: 14766, Pages: 103-115 Pages count : 13 DOI: 10.1007/978-3-031-62792-7_7 | ||||
| Tags | Graph cluster editing · Approximation algorithm · Performance guarantee · Clustering complexity | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (2)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
| 2 | Russian Science Foundation | 22-11-20019 |
Abstract:
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.
Cite:
Il’ev A.
, Il’ev V.
Clustering Complexity and an Approximation Algorithm for a Version of the Cluster Editing Problem
In compilation 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
In compilation 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
Dates:
| Submitted: | Feb 20, 2024 |
| Published print: | Jun 18, 2024 |
| Published online: | Jun 18, 2024 |
Identifiers:
| Scopus: | 2-s2.0-85198437227 |
| OpenAlex: | W4399743146 |
Citing:
Пока нет цитирований