CODEWITHSUNDEEP
mathgraph-algorithmant-colony
gilan
gilan

Reputation: 11

clique based on ant colony

I want to find all k-clique in undirected graph. Hence I need to exact algorithm based on ant colony for finding all k-clique in graph. For example, consider this adjacent matrix:

0 1 1 0 0
1 0 1 1 0
1 1 0 1 1
0 1 1 0 1
0 0 1 1 0

In this adjacent matrix we have three 3-clique: (1,2,3),(2,3,4),(3,4,5)

I want to find this k-clique in every graph. note=K is input in K-clique algorithm.

Upvotes: 1

Views: 271

Answers (2)

Novak
Novak

Reputation: 4783

Retagged to include ant-colony tag, but Andrei is correct-- ant-colony optimization won't break the NP-Complete barrier, and the k-clique problem in particular doesn't even have an approximation algorithm. (Approximation algorithm cannot exist, if I remember correctly, unless P=NP.)

The most recent survey I happen to know of talking about ACO and the clique problem in particular is about six years old, linked below. It's a very nice study, including exhaustive simulation/benchmarks for four separate techniques, and one immediate conclusion is that in 2006, even state of the art ACO approaches were not guaranteed to get the actual maximum clique in the benchmark problems.

http://liris.cnrs.fr/Documents/Liris-1847.pdf

Upvotes: 1

Andrei
Andrei

Reputation: 56688

As long is K is arbitrary value being a problem input, the k-clique problem is NP-complete, which means there is nothing essentially better then just a brute force algorithm - take every subgraph of K nodes and check whether it represents a clique. Implementation details of this idea via backtracking can be found here.

Upvotes: 2

Related Questions