Нахождение максимальных бикликов

Question

У меня есть проблема, которую я смог смоделировать как поиск максимальных бикликов (полных двудольных графов) в двудольном графе.Мне известен алгоритм Брона-Кербоша для определения максимальных кликов, и мне кажется, что должен быть способ выразить бикликовую проблему как кликовую.У кого-нибудь есть решение, либо для формирования проблемы с бикликом в виде клики, либо в качестве доступного алгоритма для непосредственного обнаружения бикликов?

Answer 1

Существует следующая реализация максимального перечисления biclique алгоритм из Согласованные алгоритмы для генерации всех максимальных biclique by Alexe et.al. .

Теоретическое время работы: O(Bn^3), где B - количество максимальных бикликов.

Answer 2

Существует более быстрый алгоритм Нагараджана, Кингсфорда "Выявление геномных реассортов среди штаммов гриппа путем перечисления максимальных бикликов", который работает в O(n^2).