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 ?
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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 ?
Name |
---|
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 :(
Thanks , i'm seeking for O(n) algorithm , but that seems to be impossible right ?
I'm afraid it is impossible :'(
This problem is known to be NP-hard. If someone finds even a polynomial solution, not necessary linear, he will get a Millenium Prize.
So you are telling me that i spent the night trying to solve a millenium prize algorithm ... lol
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.
Okay you got me. I'll try that may be i will come up with something.