一种新颖且实用的算法改进方法，用于枚举k-部分图中的最大k-部分团及其子团 陈成（Cheng Chen）、 费萨尔·N·阿布-赫扎姆（Faisal N. Abu-Khzam）、 莱文特·多伊查克（Levente Dojcsak）和 迈克尔·A·兰斯顿（Michael A. Langston）

《Algorithms》：A Novel and Practical Algorithmic Enhancement for Enumerating Maximal and Maximum k-Partite Cliques in k-Partite Graphs Cheng Chen, Faisal N. Abu-Khzam, Levente Dojcsak and Michael A. Langston

　　

摘要

一个k部分图是指其顶点可以被划分为k个不相交的部分集合，并且这些集合之间允许存在边，但集合内部不允许有边。在这样的图中，一个最大的k部分团是一个子图，它包含来自每个部分集合的至少一个顶点，并且所有边都是允许存在的；此外，这个子图不能再通过添加额外的顶点来扩大。显然，最大的k部分团也是大小最大的k部分团。这里报告的结果描述了对之前发表的最佳算法的一种新颖且实用的改进，用于枚举这些特殊的子图。这种新方法的相对性能依赖于隐式的边添加和搜索树剪枝，并且是在使用伪随机数据及真实世界数据构建的图上进行评估的。