Re: [igraph] clique

[Tamas Nepusz]

> well this question is not strictly related to iGraph, but maybe  
> somebody knows a "fast" algorithm for finding maximal cliques in a  
> graph (+/- 300 nodes)? Any language will do: C, python,  
> matlab, ...anything. Or just a paper where the implementation is  
> described.
Try the following and the citations therein:

Etsuji Tomita and Akira Tanaka and Haruhisa Takahashi: The worst-case  
time complexity for generating all maximal cliques and computational  
experiments. Theoretical Computer Science 363:28--42, 2006.

Note that igraph currently does not include this algorithm and thus  
the maximal clique finding algorithm is somewhat slow on very sparse  
graphs (this may look controversial, but actually igraph looks for the  
maximal independent sets in the complementer graph, so that's why). I  
just started working on a proper maximal clique finding algorithm  
implementation in igraph and it will probably find its way into 0.6.

--
Tamas