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 ?
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.11.2024 23:14:02 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
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.