Дата публикации: 2022

Дата публикации в реестре: 2022-10-06T22:28:22Z

Аннотация:

Изучается генерическая сложность проблемы кластеризации графов с ограничениями на число кластеров. В этой проблеме структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на ограниченное число попарно непересекающихся групп (кластеров) так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Строится подпроблема этой проблемы, для которой, при условии P 6= NP и P = BPP, не существует полиномиального генерического алгоритма.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2022. № 57. С. 91-97