The Shape of the Search Tree for the Maximum Clique Problem, and the Implications for Parallel Branch and Bound

Ciaran McCreesh, Patrick Prosser

Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multi-core thread-parallel adaptations of a state-of-the-art branch and bound a…