TP4 - Threads - AEDS III

´
TRABALHO PRATICO 4:
Problemas NP-Completo e Programacao Paralela

Resumo. Este relat´ rio descreve a modelagem do problema de encontrar os o cliques maximais em grafos atrav´ s de algoritmos sequenciais baseados em e backtracking e utilizando paralelismo.

1. INTRODUCAO
¸˜
Neste trabalho foram desenvolvidos algoritmos que buscam a resolucao do problema do
¸˜
clique, de formas sequencial e paralela. Na teoria dos grafos, um clique em um grafo
´
n˜ o-orientado e o subconjunto de v´ rtices tal que, cada par de v´ rtices deste subconjunto a e e sejam conectados por uma aresta, ou seja, o subgrafo formado por esse subconjunto de
´
v´ rtices e completo. e ´
Na computacao, o problema do clique e encontrar o clique m´ ximo de um grafo ou
¸˜
a todos os cliques que podem ser formados em um grafo qualquer. O objetivo deste trabalho
´
e implementar duas solucoes para o problema do clique. Uma solucao sequencial, baseada
¸˜
¸˜ em backtracking, e uma solucao paralela utilizando a biblioteca pthreads.
¸˜

2. SOLUCAO PROPOSTA
¸˜
´
Inicialmente o problema dado e em relacao a busca das relacoes entre membros em uma
¸˜
¸˜ rede social fict´cia. A relacao entre cada membro foi mapeada como um grafo n˜ o orienı
¸˜
a tado G = (V, A), em que, os v´ rtices representam cada membro da rede social e as arestas e ´ representam a relacao entre membros da rede. Uma relacao de amizade e estabelecida
¸˜
¸˜ quando uma aresta liga dois v´ rtices diferentes do grafo. e O problema a ser resolvido consiste em encontrar o maior grupo de usu´ rios da a ´ rede, sendo que todos eles dever˜ o ter amizades entre si. Esse problema e um problema a computacional e matem´ tica denomidado Problema do Clique. Na teoria dos grafos, um a ´ clique e definido como sendo um subgrafo completo contido em outro grafo de tamanho igual ou maior, sendo um grafo completo aquele em que todos os v´ rtices s˜ o conectados e a
´
por uma aresta. Um grafo G = (V, A),