- Listing all maximal cliques in large sparse real-world graphs.
D. Eppstein, M. Löffler, and D. Strash.
J. Experimental Algorithmics 18 (3): 3.1, 2013 (special issue for SEA).This paper combines our theoretical results on clique-finding algorithms from ISAAC 2010 with our experimental results on the same algorithms from SEA 2011. We show how to list all maximal cliques in graphs of bounded degeneracy in time that is linear in the size of the graph and near-optimal in the degeneracy, and we show that low degeneracy explains the good behavior of the algorithm in our experiments on large real-world social networks.