  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 algorithm for the maximum clique problem, and
provide a novel explanation as to why they are successful. We show that load
balance is sometimes a problem, but that the interaction of parallel search
order and the most likely location of solutions within the search space is
often the dominating consideration. We use this explanation to propose a new
low-overhead, scalable work splitting mechanism. Our approach uses explicit
early diversity to avoid strong commitment to the weakest heuristic advice, and
late resplitting for balance. More generally, we argue that for branch and
bound, parallel algorithm design should not be performed independently of the
underlying sequential algorithm.
