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

doi:10.17223/20710410/46/6

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О генерической сложности проблемы кластеризации графов	2 MB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/46/6

#генерическая сложность

#кластеризация графов

Title: О генерической сложности проблемы кластеризации графов
Title: On generic complexity of the graph clustering problem
Creator: Рыбалов, Александр Николаевич
Date: 2019
DOI: 10.17223/20710410/46/6
Description: Генерический подход к алгоритмическим проблемам предложен Мясниковым, Каповичем, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность проблемы кластеризации графов. В этой задаче структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на попарно непересекающиеся группы (кластеры) так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Доказывается, что при условии P = NP и P = BPP для проблемы кластеризации графов не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность частот которого при увеличении размера экспоненциально быстро сходится к 1.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2019. № 46. С. 72-77
Language: rus

Created: 11-03-2020

394 Visitors

255 Hits

146 Downloads

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