On Problem of Finding all Maximal Induced Bicliques of Hypergraph

Abstract

The problem of finding all maximal induced bicliques of a hypergraph is considered in this paper. A theorem about 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 and computational experiments with its applying are presented

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