Solving the maximum clique problem using PUBB

Given an (undirected) graph G=(V, E), a clique of G is a subset of vertices in which every pair is connected by an edge. The problem of finding a clique of maximum size is a classical NP-hard problem, and many algorithms, both heuristic and exact, have been proposed. While the philosophy behind the heuristic algorithms varies greatly, almost all of the exact algorithms are designed in the branch-and-bound framework. As is well known, branch-and-bound is well suited to parallelization, and PUBB is a software utility which implements a generic version of it. The authors show effectiveness of parallelization of branch-and-bound for the maximum clique problem. Especially, by using PUBB with good heuristics and branching techniques, they were able to solve five previously unsolved DIMACS benchmark problems to optimality