BUSCA DE SUBGRAFOS POR MEIO DE RÓTULOS

XXXVII Encontro de Iniciação Científica

Luis Filipe Velasco da Silva, HENRIQUE SANTOS DE ANDRADE, Claudia Linhares Sales

Grafos são amplamente usados em diversas aplicações, como encaminhamento de pacotes na internet, cálculo da melhor rota para chegar a um destino ou descobrir a forma mais eficiente para a distribuição de recursos. Entretanto, por diversos motivos, encontrar ou reconhecer uma parte do grafo pode se fazer necessário para a execução de uma tarefa. Em razão disso, a busca de subgrafos torna-se uma operação importante e objeto de busca de algoritmos eficientes para fazê-lo.  Nessa pesquisa, em específico, trabalha-se com grafos rotulados. Os subgrafos procurados possuem determinadas características, tais como ser acíclico e possuir no máximo uma distância δ entre seus vértices de mesmo rótulo no grafo. Esse δ é um parâmetro passado na função que representa a proporção entre o grafo que está sendo procurado e o subgrafo retornado como resposta da função. Para os testar a função implementada, foi utilizado um conjunto de dados reais baseados na análise da estrutura topológica da interação entre proteínas, formando um grafo com 2361 vértices e 7181 arestas. Quando executado o algorítimo, a procura por um certo subgrafo linear, em um processador i5 com 4 GB de memória RAM,  encontra as soluções possíveis em cerca de 70 milisegundos. O algorítimo implementado ainda não permite grafos com nós com mais de um filho, devido à complexidade. Essa será  entretanto a próxima etapa deste trabalho.

Palavras-chave: busca. subgrafos. grafos. rotulados.

Encontros Universitários da UFC, Fortaleza, v. 3, 2018

1061