CS 269S, Winter 2011: Theory Seminar
ICS 243
17 May 2011:

Speaker: Darren Strash

New Theoretical and Practical Results for Listing All Maximal Cliques in Sparse Graphs

Listing all maximal cliques in a given graph is an important combinatorial problem that has applications in bioinformatics, social network analysis, and document clustering (to name a few). Though there are many algorithms that can list all maximal cliques, there is no algorithm which is sufficient for large, sparse graphs in practice. Specifically, those algorithms that are designed for sparse graphs are slow, and those algorithms that are fast in practice require an adjacency matrix, which limits their use to small graphs. In this talk, I will describe a new algorithm for listing all maximal cliques that has a near-optimal running time, and works well in practice for large, sparse graphs.

This is joint work with David Eppstein and Maarten Loffler.

These results appeared in ISAAC 2010 ( http://dx.doi.org/10.1007/978-3-642-17517-6_36 ) and SEA 2011 ( http://dx.doi.org/10.1007/978-3-642-20662-7_31 ).