GraphStream Users

Archives de la liste Aide


Re: Maximal Clique


Chronologique Discussions 
  • From: "Frédéric Guinand" <frederic.guinand AT gmail.com>
  • To: Rodrigo Lins <lins.oliveira AT gmail.com>
  • Cc: graphstream-users AT litislab.fr, frederic.guinand AT gmail.com
  • Subject: Re: Maximal Clique
  • Date: Mon, 20 Jun 2011 14:04:36 +0200
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:reply-to:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; b=MgayfkRRf1t+sfPFKZAj7Mu6vRyRzRPcN/1vj+MSabeO1f+k/Gw6YX4sxKNkDwuATo IWsb1bDuxh1fIQGlYv8lCGHlp8y4RDkEoYFdr9mnI97/J6/2BAALcjmH2xzwWVQY/tp0 tyhmK1NMJ9HO2QGhWoG5pyzpyaK572ezWFeaI=


Hello Rodrigo,

What is the size of your graph(s)?

I can try to implement a quick'n'dirty algo if you really need this urgently.


Frederic


Rodrigo Lins wrote:
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,
Rodrigo.

On Sun, Jun 19, 2011 at 5:56 PM, Stefan Balev <stefan.balev AT gmail.com <mailto:stefan.balev AT gmail.com>> 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 ?

Cheers,

--
Stefan


2011/6/19 Rodrigo Lins
<lins.oliveira AT gmail.com

<mailto:lins.oliveira AT gmail.com>>:
> 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

<mailto: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