Exact Parallel Maximum Clique Algorithm for General and Protein Graphs

详细信息    查看全文

• 作者：Matja啪 Depolli ; Janez Konc ; Kati Rozman ; Roman Trobec ; Du拧anka Jane啪i膷
• 刊名：Journal of Chemical Information and Modeling
• 出版年：2013
• 出版时间：September 23, 2013
• 年：2013
• 卷：53
• 期：9
• 页码：2217-2228
• 全文大小：745K
• 年卷期：v.53,no.9(September 23, 2013)
• ISSN：1549-960X

文摘

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.