О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров Full article
Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
---|---|---|---|
Output data | Year: 2023, Number: 60, Pages: 114-119 Pages count : 6 DOI: 10.17223/20710410/60/10 | ||
Tags | генерическая сложность, кластеризация графа | ||
Authors |
|
||
Affiliations |
|
Funding (1)
1 | Russian Science Foundation | 22-11-20019 |
Abstract:
Изучается генерическая сложность проблемы кластеризации графов с ограничением p на размеры кластеров при p 3. В этой задаче структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на попарно непересекающиеся группы (кластеры) ограниченного числом p размера так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Доказывается, что при условии P= NP и P = BPP для этой проблемы не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность частот которого при увеличении размера экспоненциально быстро сходится к 1
Cite:
Рыбалов А.Н.
О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. №60. С.114-119. DOI: 10.17223/20710410/60/10 WOS Scopus РИНЦ OpenAlex
О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. №60. С.114-119. DOI: 10.17223/20710410/60/10 WOS Scopus РИНЦ OpenAlex
Dates:
Published print: | Jun 19, 2023 |
Published online: | Jun 19, 2023 |
Identifiers:
Web of science: | WOS:001065160100010 |
Scopus: | 2-s2.0-85175462470 |
Elibrary: | 53971752 |
OpenAlex: | W4405724402 |
Citing:
Пока нет цитирований