Clique number - heuristics

[SeventhStar]

Hi,
I need to find the clique number of a non-oriented graph. As far as I know this is an np-complete poblem so the complexity of a standart algorithm will be around O(n^3) and with the graph being with 10 000 nodes max I think a full solve is impossible.

So I'm looking for a heuristical (is this correct to say :rolleyes: ) solve. I only managed to find the Reactive Local Search algorithm but it's only source. It is good as the complexity is linear to the edges but they dont offer any explanations and unofrtunately I have to understand it to use it.

Does anyone has any good ideas on the matter? I'd settle for O(n^2) complexity. Pseudo code will also do...

Thanks in advance for any help!

[RoboTact]

There is no good algorithm for any such problem unless you provide features of your data.

[SeventhStar]

what kind of features are you talking about?

[RoboTact]

For example, graph is planar/have limited vertex degree/etc. There are also approximate algorithms.

[SeventhStar]

Nope... we don't know any of this.
Only a graph given by it's number of nodes and the exact connections is given. Nothing more. It is however signle-weight and non-oriented. But that's all (and this doesnt matter for finding the max clique)

PS As I said It seem impossible to use a full solve on this. So I am looking for a heuristical algorithm. Monte Carlo style would be better (giving some answer although it may be incorrect)