Utilização de Regras de Redução em Grafos Power Law: Problema da Cobertura por Vértices

Abstract

Cobertura Mínima de Vértices é o menor conjunto de vértices cuja remoção desconecta completamente o grafo. Neste artigo realizamos experimentos com grafos com distribuição de grau de uma lei de potência (power law), aplicando regras de redução antes da aplicação de um algoritmo guloso que encontra uma cobertura mínima de vértices. Nos experimentos foi comparado o resultado da execução de um algoritmo guloso contra os resultados da aplicação das regras de redução antes da utilização do algoritmo guloso; resultando em uma cobertura 1% menor e chegando a diminuir em até 86% do tempo de execução em uma das instâncias utilizadas.