Discrepancy-free orders and improved algorithm for the maximum clique problem

Abstract

An efficient new algorithm for the Maximum Clique Problem is presented within this paper. After resuming the known algorithm of Carraghan & Pardalos and the cliquer of Östergård, a special register function is introduced, which allows reordering the nodes of a graph in such a way, that Östergård’s algorithm runs significantly faster than upon other usual orders of nodes. After the definition of discrepancy-free orders of the nodes, a sorting algorithm is specified on the nodes, producing a discrepancy-free order of them. Finally a combination of the sorting algorithm with Östergård’s algorithm is given as a new solver for the Maximum Clique Problem. Benchmark results on DIMACS graphs are presented in table format.