Mr.Awesome's blog

Complete graph
By Mr.Awesome, history, 9 years ago, In English

Hi CF's .

Is there any algorithm that can find the biggest Complete graph inside a graph.

I searched a little but i didn't find any resources , is such algorithm even exist ?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Good day to you

Complete graph inside graph is called "Clique" so you can try to search this term and you will find more results.

Anyway algorithms searching for clique (unless specific cases) are exponential :(

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Thanks , i'm seeking for O(n) algorithm , but that seems to be impossible right ?

    → Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I assume you are trying to apply this to Today's D, since I was thinking of the same thing. Try drawing example graphs and you might notice some special properties of the cliques.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Okay you got me. I'll try that may be i will come up with something.

    → Reply