RUS  ENG
Полная версия
ЖУРНАЛЫ // Журнал Сибирского федерального университета. Серия «Математика и физика» // Архив

Журн. СФУ. Сер. Матем. и физ., 2021, том 14, выпуск 5, страницы 638–646 (Mi jsfu950)

Эта публикация цитируется в 1 статье

On problem of finding all maximal induced bicliques of hypergraph

[О задаче перечисления всех максимальных индуцированных биклик гиперграфа]

Aleksandr A. Soldatenko, Daria V. Semenova

Siberian Federal University, Krasnoyarsk, Russian Federation

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

Ключевые слова: гиперграф, максимальные индуцированные биклики, алгоритм поиска.

УДК: 519.17+519.7

Получена: 10.03.2021
Исправленный вариант: 21.05.2021
Принята: 20.06.2021

Язык публикации: английский

DOI: 10.17516/1997-1397-2021-14-5-638-646



Реферативные базы данных:


© МИАН, 2024