MSc Student of D1

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Finding cliques in networks is of practical importance, yet the clique-problem is widely believed to be intractable on general instances. However, many real-world data such as the internet, social networks or protein-protein interaction networks have a specific, namely scale-free, structure: Their degree sequence follows a power law. This talk presents theoretical bounds and experimental results for two algorithms that exploit this structure to find k-cliques. It is proven that on inhomogeneous random graphs the k-clique problem is tractable on average.

Tobias Friedrich

--email hidden

passcode not visible

logged in users only