| Article ID: | iaor201526252 |
| Volume: | 9 |
| Issue: | 5 |
| Start Page Number: | 949 |
| End Page Number: | 960 |
| Publication Date: | Jun 2015 |
| Journal: | Optimization Letters |
| Authors: | Prosser Patrick, McCreesh Ciaran |
| Keywords: | programming: branch and bound |
The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch‐and‐bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.