GraphStream Users

Archives de la liste Aide

Re: Maximal Clique

Chronologique Discussions 
  • From: Rodrigo Lins <lins.oliveira AT>
  • To: graphstream-users AT
  • Cc: frederic.guinand AT
  • Subject: Re: Maximal Clique
  • Date: Sun, 19 Jun 2011 18:08:33 -0300
  • Domainkey-signature: a=rsa-sha1; c=nofws;; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=n/LcO8do9+WEpalLvh/M5X/9JCfXc0VVvpqvIKsBjAqYtpAxlvs+1HFpdxcX4GVfUY 3n65E34vR6Z0BNTnM7MBrf6cLHGf6Out5nGuwOKo1fRMIJYvz/l6E7GOdsHbvbXvD89m n6uPCnBShBVjuE8diZTkW/Xpn0tlvIM85e2Hw=

Hi Stefan,
I need only to find a maximum cardinality.
I mount the graph based in a correlation algorithm.
I`m looking for a implemented algorithm or if the graph stream have one implementation.

Thanks a lot,

On Sun, Jun 19, 2011 at 5:56 PM, Stefan Balev <stefan.balev AT> wrote:
Hi Rodrigo,

If you can wait, just use a brute force approach. Is your graph
weighted or you just want to find a maximum cardinality clique ?



2011/6/19 Rodrigo Lins <lins.oliveira AT>:
> 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>
>> 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:
>> 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