|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
Математические основы информатики и программирования
О генерической сложности проблемы кластеризации графов
А. Н. Рыбалов Институт математики им. С. Л. Соболева СО РАН, г. Омск, Россия
Аннотация:
Генерический подход к алгоритмическим проблемам
предложен Мясниковым, Каповичем, Шуппом и
Шпильрайном в 2003 г. В рамках этого подхода
рассматривается поведение алгоритмов на множествах
почти всех входов. В данной работе изучается генерическая
сложность проблемы кластеризации графов. В этой задаче
структура взаимосвязей объектов задаётся с помощью графа,
вершины которого соответствуют объектам, а рёбра соединяют похожие объекты.
Требуется разбить множество объектов на попарно
непересекающиеся группы (кластеры) так,
чтобы минимизировать число связей между кластерами
и число недостающих связей внутри кластеров. Доказывается, что при условии
$\text{P} \neq \text{NP}$ и $\text{P}=\text{BPP}$ для проблемы кластеризации
графов не существует полиномиального сильно генерического алгоритма.
Сильно генерический алгоритм решает проблему не на всём множестве
входов, а на подмножестве, последовательность частот которого при увеличении размера
экспоненциально быстро сходится к 1.
Ключевые слова:
генерическая сложность, кластеризация графа.
Образец цитирования:
А. Н. Рыбалов, “О генерической сложности проблемы кластеризации графов”, ПДМ, 2019, № 46, 72–77
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm685 https://www.mathnet.ru/rus/pdm/y2019/i4/p72
|
Статистика просмотров: |
Страница аннотации: | 117 | PDF полного текста: | 29 | Список литературы: | 15 |
|