Сибирский федеральный университет

Тип публикации: статья из журнала

Год издания: 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

Место издания: Красноярск

Издатель: Сибирский федеральный университет

• Soldatenko Aleksandr A. (Siberian Fed Univ, Krasnoyarsk, Russia)
• Semenova Darla (Siberian Fed Univ, Krasnoyarsk, Russia)

• Web of Science Core Collection
• Scopus
• Ядро РИНЦ (eLIBRARY.RU)