Számítástudományi és Információelméleti Tanszék

Egy gráf maximális klikkjeinek megtalálása nehéz probléma. Már az a kérdés is NP-teljes, hogy a gráf tartalmaz-e adott méretű klikket. Gyakorlatban előforduló gráfokra azonban sokszor megoldható a probléma. Ezzel kapcsolatban elméleti eredmények is vannak: Parameterized Clique on Scale-Free Networks, Tobias Friedrich and Anton Krohmer, 2012 Ezeknek az eredményeknek a gyakorlati alkalmazását korlátozza, hogy nagy gráfok esetén szükség lenne jól skálázható elosztott algoritmusokra is. Nehéz az éleket úgy partícionálni, hogy kevés klikket vágjunk vele több részre. A feladat a meglévő algoritmusok skálázhatóságának vizsgálata, és jobban skálázható algoritmusok keresése.