Algoritmos para o problema da clique máxima com paralelismo de bits

Este trabalho aborda o Problema da Clique Máxima (PCM) em grafos, um pro blema NP-Completo bem conhecido na teoria dos grafos e na otimização combinatória. A maioria dos algoritmos de branch-and-bound estado da arte utiliza a heurística de co loração gulosa tanto para determinar a ordem de ramificação quanto para obter limites superiores. Em muitos casos, as diferenças nos ambientes computacionais podem tornar a comparação dos resultados menos precisa. Neste estudo, realizamos uma comparação com putacional do algoritmo MCS, apresentado no framework unificado para PCM de [Carmo and Züge(2012)], com dois algoritmos que utilizam paralelismo de bits por meio da estru tura Bitmap Roaring. Essa estrutura mostrou-se eficiente em aproveitar o paralelismo de bits proposto para os algoritmos mais recentes.