О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров | Sciact - Система учета научной деятельности ИМ СО РАН

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

Журнал

Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263

Вых. Данные

Год: 2023, Номер: 60, Страницы: 114-119 Страниц : 6 DOI: 10.17223/20710410/60/10

Ключевые слова

генерическая сложность, кластеризация графа

Авторы

Рыбалов А.Н. ¹

Организации

1	Институт математики им. С. Л. Соболева СО РАН, г. Омск, Россия

Информация о финансировании (1)

Российский научный фонд

22-11-20019

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

Рыбалов А.Н.
О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. №60. С.114-119. DOI: 10.17223/20710410/60/10 WOS Scopus РИНЦ OpenAlex

Опубликована в печати:	19 июн. 2023 г.
Опубликована online:	19 июн. 2023 г.

Web of science:	WOS:001065160100010
Scopus:	2-s2.0-85175462470
РИНЦ:	53971752
OpenAlex:	W4405724402

Пока нет цитирований