New Algorithms for Enumerating All Maximal Cliques
New Algorithms for Enumerating All Maximal Cliques
复制标题
DOI：
10.1007/978-3-540-27810-8_23
复制
发表时间：
2004-07
期刊：
影响因子：
--
通讯作者：
K. Makino;T. Uno
中科院分区：
文献类型：
--
作者：
K. Makino;T. Uno
本文考虑了n个顶点和中边的（二部）图G =（V，E）中所有极大（二部）团的生成问题.我们提出了两个算法枚举所有的最大团。一个是在O（n2）空间中的O（M（n））时间延迟，另一个是在O（n+m）空间中的O（Δ4）时间延迟，其中Δ表示G的最大度，M（n）表示两个n阶矩阵相乘所需的时间，后者需要O（nm）时间作为预处理.第一个算法以O（M（n））时间延迟和O（n2）空间运行，这直接遵循非二分情况的算法。第二个算法的时间延迟为O（Δ3），空间复杂度为O（n+m），第三个算法的时间延迟为O（Δ2），空间复杂度为O（n+m+NΔ），其中N表示G中最大二部团的个数，两个算法的预处理时间都为O（nm）.此外，计算实验表明，我们的算法稀疏图有显着良好的性能，这是随机生成的图，出现在现实世界中的问题。
In this paper, we consider the problems of generating all maximal (bipartite) cliques in a given (bipartite) graphG=(V,E) withnvertices andmedges. We propose two algorithms for enumerating all maximal cliques. One runs with O(M(n)) time delay and in O(n2) space and the other runs with O(Δ4) time delay and in O(n+m) space, where Δ denotes the maximum degree ofG,M(n) denotes the time needed to multiply twon×nmatrices, and the latter one requires O(nm) time as a preprocessing.For a given bipartite graphG, we propose three algorithms for enumerating all maximal bipartite cliques. The first algorithm runs with O(M(n)) time delay and in O(n2) space, which immediately follows from the algorithm for the non-bipartite case. The second one runs with O(Δ3) time delay and in O(n+m) space, and the last one runs with O(Δ2) time delay and in O(n+m+NΔ) space, whereNdenotes the number of all maximal bipartite cliques inGand both algorithms require O(nm) time as a preprocessing.Our algorithms improve upon all the existing algorithms, whenGis either dense or sparse. Furthermore, computational experiments show that our algorithms for sparse graphs have significantly good performance for graphs which are generated randomly and appear in real-world problems.