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

Дата публикации в реестре: 2023-12-05T16:07:49Z

Аннотация:

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

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

Источник: Прикладная дискретная математика. 2023. № 60. С. 114-119