0

我是理论计算机的新手，我被要求做一个在多项式时间内工作的算法，让 K-CLIQUE 证明它属于 P。

我正在考虑一种算法，它采用 n 个顶点的图形，对于每个顶点，例如 S0，我检查它有多少个团，例如 (s1 , s2 , s5) ，然后检查 S1 是否有团s2, s5 然后我去 s2 并检查它是否与 s5 有一个集团。

但我觉得我的生活很复杂，对吧？

对算法有什么建议吗？我知道这很容易，也许有人会帮助我了解查找算法的工作原理。

赞赏

4

1 回答 1

1

作为提示，如果k是一个常数，那么恰好k个节点的集合的数量是 O(n k )。如果您尝试其中的每一个会发生什么？

于 2015-12-16T02:30:33.007 回答