GraphStream Users

Archives de la liste Aide

Re: Maximal Clique

Chronologique Discussions 
  • From: Rodrigo Lins <lins.oliveira AT>
  • To: frederic.guinand AT
  • Cc: graphstream-users AT
  • Subject: Re: Maximal Clique
  • Date: Mon, 20 Jun 2011 10:10:38 -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=Bv/jsykJq4qV5oRVx0UEEaFVMNEtFyASPlmCXkcMwr4O0SxUVUsIESS4KJrA4vkNhs AwGh/ODdQi9stUEuQsTJRNvLIYF2vCZieLPkMnou1wspdR7wOZEuWC9on0bArW/P9hHG 7vmoBMHrgtjhLgJ67+uLahQlfOVPmZ6gkLLos=

Thanks Frederic,
My graph have at the maximum 140 nodes and 140*140 vertices.
The computational effort it's no a problem. I need only to make an image with the graph.
I have found this implementation (
but i'm using the Graph Stream graph objects and i dont want to use the JUNG framework.
If you can make an implementation of this algorithm i'll be very happy!
Thanks for your patience and your help!
If you can't do this, let me know, and I will try to use a JUNG or make an implementation!

Thanks a lot,

2011/6/20 Frédéric Guinand <frederic.guinand AT>

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.


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,

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

    > Thanks Frederic for your answer.
    > But I really need to find de cliques in a graph, and I know this
    > 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