title: Exact parallel maximum clique algorithm for general and protein graphs.
abstract: A new exact parallel maximum clique algorithm MaxCliquePara, which finds the maximum clique (the fully connected subgraph) in undirected general and protein graphs, is presented. First, a new branch and bound algorithm for finding a maximum clique on a single computer core, which builds on ideas presented in two published state of the art sequential algorithms is implemented. The new sequential MaxCliqueSeq algorithm is faster than the reference algorithms on both DIMACS benchmark graphs as well as on protein-derived product graphs used for protein structural comparisons. Next, the MaxCliqueSeq algorithm is parallelized by splitting the branch-and-bound search tree to multiple cores, resulting in MaxCliquePara algorithm. The ability to exploit all cores efficiently makes the new parallel MaxCliquePara algorithm markedly superior to other tested algorithms. On a 12-core computer, the parallelization provides up to 2 orders of magnitude faster execution on the large DIMACS benchmark graphs and up to an order of magnitude faster execution on protein product graphs. The algorithms are freely accessible on http://commsys.ijs.si/~matjaz/maxclique.
authors: Jožef Stefan Institute , Jamova 39, SI-1000 Ljubljana, Slovenia.
authors: Matjaž
authors: M
authors: Depolli
authors: Janez
authors: J
authors: Konc
authors: Kati
authors: K
authors: Rozman
authors: Roman
authors: R
authors: Trobec
authors: Dušanka
authors: D
authors: Janežič
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D008958:Models, Molecular; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*; D013997:Time Factors
chemical_list: D011506:Proteins