Тип публикации: статья из журнала
Год издания: 2021
Идентификатор DOI: 10.17516/1997-1397-2021-14-5-638-646
Ключевые слова: hypergraph, maximal induced bicliques, search algorithm, гиперграф, максимальные индуцированные биклики, алгоритм поиска
Аннотация: The problem of finding all maximal induced bicliques of a hypergraph is considered in this paper. Theorem on connection between induced bicliques of the hypergraph H and corresponding vertex graph L2(H) is proved. An algorithm for finding all maximal induced bicliques is proposed. Results of computational experiments with the use of Показать полностьюthe proposed algorithm are presented. В работе рассматривается задача поиска всех максимальных индуцированных биклик гиперграфа. Доказана теорема о связи индуцированных биклик гиперграфа H и вершинного графа L2(H). Предложен алгоритм нахождения всех максимальных индуцированных биклик. Приведена теоретическая оценка сложности предлагаемого алгоритма и доказательство его корректности. Приведены вычислительные эксперименты. The problem of finding all maximal induced bicliques of a hypergraph is considered in this paper. Theorem on connection between induced bicliques of the hypergraph H and corresponding vertex graph L2(H) is proved. An algorithm for finding all maximal induced bicliques is proposed. Results of computational experiments with the use of the proposed algorithm are presented. © Siberian Federal University. All rights reserved.
Журнал: Журнал Сибирского федерального университета. Серия: Математика и физика
Выпуск журнала: Т. 14, № 5
Номера страниц: 638-646
ISSN журнала: 19971397
Место издания: Красноярск
Издатель: Сибирский федеральный университет