ГлавнаяАрхивО генерической сложности ограниченной проблемы кластеризации графов

О генерической сложности ограниченной проблемы кластеризации графов | Прикладная дискретная математика. 2022. № 57. DOI: 10.17223/20710410/57/6

Изучается генерическая сложность проблемы кластеризации графов с ограничениями на число кластеров. В этой проблеме структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на ограниченное число попарно непересекающихся групп (кластеров) так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Строится подпроблема этой проблемы, для которой, при условии P ≠ NP и P = BPP, не существует полиномиального генерического алгоритма.
  • Title О генерической сложности ограниченной проблемы кластеризации графов
  • Headline О генерической сложности ограниченной проблемы кластеризации графов
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 57
  • Date:
  • DOI 10.17223/20710410/57/6
Ключевые слова
генерическая сложность, кластеризация графа
Авторы
Ссылки
Krivanek M. and Moravek J. NP-hard problems in hierarchical-tree clustering // Acta Informatica. 1986. V. 23. P.311-323.
Bansal N., Blum A., and Chawla S. Correlation clustering // Machine Learning. 2004. V. 56. P. 89-113.
Shamir R., Sharan R., and Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144. No. 1-2. P. 173-182.
Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графов // Дискретный анализ и исследование операций. Сер. 1. 2006. Т. 13. №1. С. 3-11.
Ильев В. П., Ильева С.Д. О задачах кластеризации графов // Вестник Омского университета. 2016. №2. C. 16-18.
Ильев А. В., Ильев В. П. Об одной задаче кластеризации графа с частичным обучением // Прикладная дискретная математика. 2018. №42. С. 66-75.
Талевнин А. С. О сложности задачи аппроксимации графов // Вестник Омского университета. 2004. № 4. C. 22-24.
Impagliazzo R. and Wigderson A. P = BPP unless E has subexponential circuits: Derandomizing the XOR Lemma // Proc. 29th STOC. El Paso: ACM, 1997. P.220-229.
Kapovich I., Miasnikov A, Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks //j. Algebra. 2003. V. 264. No. 2. P. 665-694.
Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. Т. 31. С. 35-42.
Myasnikov A. G. and Rybalov A.N. Generic complexity of undecidable problems //j. Symbolic Logic. 2008. V. 73. No. 2. P.656-673.
Rybalov A. N. On the strongly generic undecidability of the Halting Problem // Theor.Comput. Sci. 2007. V.377. P.268-270.
Rybalov A. N. Generic complexity of Presburger arithmetic // Theory Comput. Systems. 2010. V. 46. No. 1. P.2-8.
Rybalov A. N. Generic complexity of the Diophantine problem // Groups Complexity Cryptology. 2013. V. 5. No. 1. P. 25-30.
Rybalov A. N. Generic hardness of the Boolean satisfiability problem // Groups Complexity Cryptology. 2017. V. 9. No. 2. P.151-154.
Рыбалов А. Н. О генерической сложности проблемы кластеризации графов // Прикладная дискретная математика. 2019. №46. С. 72-77.
Рыболов А. Н. О генерической сложности проблемы распознавания гамильтоновых путей // Прикладная дискретная математика. 2021. №53. С. 120-126.
О генерической сложности ограниченной проблемы кластеризации графов | Прикладная дискретная математика. 2022. № 57. DOI: 10.17223/20710410/57/6
О генерической сложности ограниченной проблемы кластеризации графов | Прикладная дискретная математика. 2022. № 57. DOI: 10.17223/20710410/57/6