Contact Information

Computer Science Department
Colgate University
McGregory Hall, 3rd Floor
13 Oak Drive
Hamilton, NY 13346
(tel) 315.228.7719
Charlotte Jablonski, Administrative Assistant
cjablonski@colgate.edu

Event Detail

Dept Tea: Speeding Up Maximum Clique Computation with Graph Partitioning

Start: Tuesday, October 17, 2017, 11:30 a.m.
End: Tuesday, October 17, 2017, 12:20 p.m.
Location: 319 McGregory Hall

Speaker: Rohan Chaudhari '19

Abstract: In a social network, a clique is a group of mutual friends. A clique is maximum if it has the largest cardinality among all cliques in the graph. This past summer, I worked with Prof. Darren Strash on speeding up maximum clique searches on large sparse graphs. While there is no known efficient algorithm to compute a maximum clique, there are numerous real-world applications, including community detection in social networks and molecular docking in computational biology. Our algorithm is a proof of concept which shows that applying advanced graph partitioning techniques to reduce graph size significantly speeds up clique finding in practice.