In problems of clustering on graphs, for a given graph G, it is required to find the cluster graph closest to it on the same set of vertices. A graph is called clustered if each of its connected components is a complete graph. The distance between two graphs is understood as the number of non-matching edges. The problem of clustering on graphs is considered, in which the sizes of clusters are bounded from above by the number s. An upper bound for the complexity of clustering an arbitrary graph for the case s = 2 is proved. An approximate polynomial algorithm for solving the problem of clustering on graphs for the case s = 3 is proposed, and an upper bound for the complexity of clustering an arbitrary graph for this case is proved.
Download file
Counter downloads: 19
- Title On the complexity of graph clustering in the problem with bounded cluster sizes
- Headline On the complexity of graph clustering in the problem with bounded cluster sizes
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 60
- Date:
- DOI 10.17223/20710410/60/6
Keywords
graph, clustering, clustering complexityAuthors
References
Schaeffer S. E. Graph clustering jj Comput. Sci. Rev. 2005. V. 1. No. 1. P. 27-64.
Ляпунов А. А. О строении и эволюции управляющих систем в связи с теорией классификации jj Проблемы кибернетики. Вып.27. М.: Наука, 1973. С. 7-18.
Фридман Г. Ш. Одна задача аппроксимации графов jj Управляемые системы. 1971. Вып. 8. С. 73-75.
Фридман Г. Ш. Об одном неравенстве в задаче аппроксимации графов jj Кибернетика. 1974. №3. С. 151.
Bansal N., Blum A, and Chawla S. Correlation clustering jj Machine Learning. 2004. V. 56. P. 89-113.
Ben-Dor A., Shamir R., and Yakhimi Z. Clustering gene expression patterns jj J.Comput. Biol. 1999. V. 6. No. 3-4. P. 281-297.
Shamir R., Sharan R., and Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144. No. 1-2. P. 173-182.
Tomescu I. La reduction minimale d'un graphe a une reunion de cliques // Discrete Math. 1974. V. 10. No. 1-2. P. 173-179.
Zahn C. T. Approximating symmetric relations by equivalence relations //j. SIAM. 1964. V. 12. No. 4. P. 840-847.
Ильев В. П., Фридман Г. Ш. К задаче аппроксимации графами с фиксированным числом компонент // Докл. АН СССР. 1982. Т. 264. №3. С. 533-538.
Фридман Г. Ш. Исследование одной задачи классификации на графах // Методы моделирования и обработки информации. Новосибирск: Наука, 1976. С. 147-177.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1984. 510 с.
On the complexity of graph clustering in the problem with bounded cluster sizes | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 60. DOI: 10.17223/20710410/60/6
Download full-text version
Counter downloads: 125