寻找最大双团

Question

5

我有一个问题，可以模拟为在二分图中查找最大的双团（完全二部图）。我知道Bron-Kerbosch算法用于检测最大团，并且我认为应该有一种方法将双团问题表达为团问题。是否有人有解决方案，无论是将双团问题形成为团问题，还是直接检测双团的可用算法？

- Muhammad Alkarouri

2个回答

1

有一种更快的算法由Nagarajan，Kingsford提出，名为“通过枚举最大二分图来揭示流感菌株之间的基因组重排”，其运行时间为O(n^2)。

- lynxoid

另一个改进：在二分图中寻找双团的一种新算法及其在多样生物数据类型整合中的应用 - 作者为Yun Zhang，Charles A Phillips，Gary L Rogers，Erich J Baker，Elissa J Chesler和Michael A Langston。 - Serge

另外一个？http://www.vldb.org/pvldb/vol13/p1359-lyu.pdf - Radio Controlled

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- polygenelubricants · Accepted Answer

以下是来自Alexe等人的《一致算法生成所有最大二分图的极大双团实现》Consensus algorithms for the generation of all maximal bicliques的极大双团枚举算法。

理论运行时间为O(Bn^3)，其中B是极大双团的数量。