Improved initial vertex ordering for exact maximum clique search

摘要

This paper describes a new initial vertexordering procedure NEW_SORT designed to enhance approximate-colour exact algorithms for the maximum clique problem (MCP). NEW_SORT considers two different vertex orderings: degree and colour-based. The degree-based vertex ordering describes an improvement over a well-known vertex ordering used by exact solvers. Moreover, colour-based vertex orderings for the MCP have been traditionally considered suboptimal with respect to degree-based ones. NEW_SORT chooses the “best” of the two orderings according to a new evaluation function. The reported experiments on graphs taken from public datasets show that a leading exact solver using NEW_SORT —and further enhanced with a strong initial solution— can improve its performance very significantly (sometimes even exponentially).