Журнал СФУ. Математика и физика / О задаче перечисления всех максимальных индуцированных биклик гиперграфа

Полный текст (.pdf)
Номер
Журнал СФУ. Математика и физика. 2021 14 (5)
Авторы
Солдатенко, Александр А.; Семенова, Дарья В.
Контактная информация
Солдатенко, Александр А.: Сибирский федеральный университет Красноярск, Российская Федерация; Семенова, Дарья В.: Сибирский федеральный университет Красноярск, Российская Федерация
Ключевые слова
hypergraph; maximal induced bicliques; search algorithm; гиперграф; максимальные индуцированные биклики; алгоритм поиска
Аннотация

В работе рассматривается задача поиска всех максимальных индуцированных биклик гиперграфа. Доказана теорема о связи индуцированных биклик гиперграфа H и вершинного графа L2(H). Предложен алгоритм нахождения всех максимальных индуцированных биклик. Приведена теоретическая оценка сложности предлагаемого алгоритма и доказательство его корректности. Приведены вычислительные эксперименты

Страницы
638–646
DOI
10.17516/1997-1397-2021-14-5-638-646
Статья в архиве электронных ресурсов СФУ
https://elib.sfu-kras.ru/handle/2311/143739