Descontaminação Distribuída de Grafos

Seja G = (V,A) um grafo conexo considerado como inicialmente contaminado. O problema de descontaminação de G consiste em extinguir essa contaminação, considerando os critérios de recontaminação de cada situação apresentada,  utilizando-se do menor número de guardas para realizar essa “limpeza”. No caso mais estrito, um nó sadio é contaminado caso entre em contato com um vizinho contaminado; um nó sadio permanece sadio somente se todos os seus vizinhos forem sadios ou estiverem guardados. Na literatura, casos como a contrução de Link Farms, i.e., conjuntos de páginas com links inseridos por webspammers visando aumentar a visibilidade de uma página alvo T, configura um caso de contaminação de grafos. Desfazer tais link farms, ou seja, descontaminar o grafo web correspondente, requer o emprego de guardas, buscando minimizar tanto o número de agentes quanto o de saltos, onde estes últimos indicam o tempo de descontaminação. No trabalho pioneiro de Luccio & Pagli, o critério de recontaminação é o de ter 50% dos vizinhos contaminados, sendo que a topologia dos grafos que representam esses conjuntos de páginas é restrita a grafos circulantes. Este trabalho apresenta Alg-D, um algoritmo assíncrono e distribuído baseado na dinâmica de Escalonamento por Reversão de Arestas. Além de descontaminar grafos conexos de topologia arbitrária, Alg-D apresenta melhores resultados dos que os encontrados na literatura para o caso de grafos circulantes.