The Shape of the Search Tree for the Maximum Clique Problem, and the Implications for Parallel Branch and Bound
Preprint
Abstract
Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multi-core threaded 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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Exact Parallel Maximum Clique Algorithm for General and Protein GraphsJournal of Chemical Information and Modeling, 2013
- Improvements to MCS algorithm for the maximum clique problemJournal of Combinatorial Optimization, 2013
- An improved bit parallel exact maximum clique algorithmOptimization Letters, 2011
- Limited discrepancy search revisitedACM Journal of Experimental Algorithmics, 2011
- An exact bit-parallel algorithm for the maximum clique problemComputers & Operations Research, 2011
- Cooperating local search for the maximum clique problemJournal of Heuristics, 2010
- Transparent Parallelization of Constraint ProgrammingINFORMS Journal on Computing, 2009
- Clique-detection models in computational biochemistry and genomicsEuropean Journal of Operational Research, 2006
- An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational ExperimentsJournal of Global Optimization, 2006
- Coping with Anomalies in Parallel Branch-and-Bound AlgorithmsIEEE Transactions on Computers, 1986