О генерической сложности ограниченной проблемы кластеризации графов Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Output data | Year: 2022, Number: 57, Pages: 91–97 Pages count : 8 DOI: 10.17223/20710410/57/6 | ||
| Tags | генерическая сложность, кластеризация графа | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 22-11-20019 |
Abstract:
Изучается генерическая сложность проблемы кластеризации графов с ограничениями на число кластеров. В этой проблеме структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на ограниченное число попарно непересекающихся групп (кластеров) так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Строится подпроблема этой проблемы, для которой, при условии P ≠ NP и P = BPP, не существует полиномиального генерического алгоритма.
Cite:
Рыбалов А.Н.
О генерической сложности ограниченной проблемы кластеризации графов
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. №57. С.91–97. DOI: 10.17223/20710410/57/6 WOS Scopus РИНЦ OpenAlex
О генерической сложности ограниченной проблемы кластеризации графов
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. №57. С.91–97. DOI: 10.17223/20710410/57/6 WOS Scopus РИНЦ OpenAlex
Identifiers:
| Web of science: | WOS:000870532200006 |
| Scopus: | 2-s2.0-85148856878 |
| Elibrary: | 49454228 |
| OpenAlex: | W4312989877 |