Um algoritmo bit-paralelo para o problema da clique máxima

Abstract

In this paper we present a branch-and-bound algorithm to find the maximum clique in a graph. The algorithm combines successfully used techniques and also makes use of a new heuristic proposal for fractional coloring create by the authors, as a procedure of upper bound and branching strategy, making use of bit-parallel operations. Computing experiments show that the coloring proposal presents a large reduction in the search tree and a good performance in high density instances.