Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, July 17, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Anton Krohmer (MPI Saarbrücken)
Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. However, in typical applications like social networks or protein-protein interaction networks, the considered graphs are scale-free, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with n nodes and power law exponent ɣ, cliques of size k can be found in time O(n^2) for ɣ ≥ 3 and in time O(n*exp(k^4)) for 2 < ɣ < 3.
Automatic MiSe System Software Version 1.4803M | admin login