GraphStream Users

Archives de la liste Aide


Re: Maximal Clique


Chronologique Discussions 
  • From: Rodrigo Lins <lins.oliveira AT gmail.com>
  • To: frederic.guinand AT gmail.com
  • Cc: graphstream-users AT litislab.fr
  • Subject: Re: Maximal Clique
  • Date: Sun, 19 Jun 2011 17:46:42 -0300
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=wDZbUelWXDE163hLgovAbvB0LAfhIjl18gXKuKUtqKCKYv7bc3a4xCky/tgLuiFKby Mm1Lfnl9mBTTo3QtqfnclTMrPdC4xfyX/FnHlwluH5PXZ41BOwiz8gASq0itss++bLK8 Q+7EtqSS7XeIUg8eq9tfY1H79T9+oie2zeWjI=

Thanks Frederic for your answer.
But I really need to find de cliques in a graph, and I know this algorithm is a NP-Hard problem.
I realy need to find the maximum cliques in a graph. I can wait.
Thanks,
Rodrigo.

2011/6/19 Frédéric Guinand <frederic.guinand AT gmail.com>

Hello Rodrigo,

The problem of finding the maximum clique in a graph is an NP-Hard problem. In other words, it is not possible to do so in a reasonable time (polynomial in the size of the graph). So, any method for finding a maximum clique is equivalent to use a brute force approach.

If you want to know more:

http://en.wikipedia.org/wiki/NP-complete
http://en.wikipedia.org/wiki/Clique_problem

What was the original problem you try to deal with?

    Bye,

        Frederic



Rodrigo Lins wrote:
Anyone knows if it is possible to find a maximal clique in a graph using GraphStream?
If it is possible what class do it?

Thanks a lot!
Rodrigo.




Archives gérées par MHonArc 2.6.16.

Top of page