A Simple Algorithm for Finding a Maximum Clique and Its Worst-Case Time Complexity
A Simple Algorithm for Finding a Maximum Clique and Its Worst-Case Time Complexity
复制标题
寻找最大派系的简单算法及其最坏情况时间复杂度
DOI：
10.1002/scj.4690210301
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
E. Tomita
中科院分区：
文献类型：
--
作者：
Miklo Shindo;E. Tomita
本文提出了一种新的算法MAXCLIQUE，它能在一个具有n个顶点的无向图中找到一个最大团，并表明其最坏情况时间复杂度为O(2n/2.863)。对于寻找顶点的最大独立集这一双重问题，Tarjan等人已经提出了一种最坏情况时间复杂度为O(2n/3)的算法[2]。然而，相比之下，我们的算法明显更简单，并且当将两种算法用于若干随机图并测量它们的平均运行时间时，证实我们的算法运行得更快。
This paper proposes a new algorithm MAXCLIQUE which finds a maximum clique in an undirected graph with n vertices, and shows that its worst-case time complexity is O(2n/2.863). For the dual problem of finding a maximum independent set of vertices, Tarjan et al. already have proposed an algorithm of worst-case time complexity O(2n/3) [2]. However, by comparison, our algorithm is remarkably simpler, and it was confirmed that it runs faster when two algorithms were used for several random graphs and their average running times were measured.