В задачах кластеризации на графах для данного графа G требуется найти ближайший к нему кластерный граф на том же множестве вершин. Граф называется кластерным, если каждая его компонента связности является полным графом. Расстояние между двумя графами понимается как число несовпадающих рёбер. Рассматривается задача кластеризации на графах, в которой размеры кластеров ограничены сверху числом s. Доказана верхняя оценка сложности кластеризации произвольного графа для случая s = 2. Предложен приближённый полиномиальный алгоритм решения задачи кластеризации на графах для случая s = 3 и доказана верхняя оценка сложности кластеризации произвольного графа для этого случая.
Скачать электронную версию публикации
Загружен, раз: 16
- Title О сложности кластеризации графа в задаче с ограничениями на размеры кластеров
- Headline О сложности кластеризации графа в задаче с ограничениями на размеры кластеров
- Publesher
Tomsk State University
- Issue Прикладная дискретная математика 60
- Date:
- DOI 10.17223/20710410/60/6
Ключевые слова
граф, кластеризация, сложность кластеризацииАвторы
Ссылки
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 с.

О сложности кластеризации графа в задаче с ограничениями на размеры кластеров | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/6
Скачать полнотекстовую версию
Загружен, раз: 122
- ВКонтакте
- РћРТвЂВВВВВВВВнокласснРСвЂВВВВВВВВРєРСвЂВВВВВВВВ
- Telegram