Encontrar Maximal Bicliques

Question

Tengo un problema que pude modelar para encontrar bicliques máximos (gráficos bipartitos completos) en un gráfico bipartito. Conozco el algoritmo de Bron-Kerbosch para detectar camarillas máximas, y me parece que debería haber una manera de expresar un problema de biclique como uno de camarilla. ¿Alguien tiene una solución, ya sea para formar un problema de biclique como clique uno, o como un algoritmo disponible para detectar bicliques directamente?

Answer 1

Hay el siguiente algoritmo implementation of maximal biclique enumeration de Consensus algorithms for the generation of all maximal bicliques by Alexe et.al..

El tiempo de ejecución teórico es O(Bn^3) donde B es el número máximo de bicliques.

Answer 2

Hay un algoritmo más rápido de Nagarajan, Kingsford "Descubriendo reordenamientos genómicos entre las cepas de Influenza mediante el recuento de bicliques máximos" que se ejecuta en O(n^2).