Utilização de Regras de Redução em Grafos Power Law: problema da cobertura por vértices

Edgar de Oliveira Cabral Filho, Mariana Oliveira da Silva, André Luís Vignatti

Resumo


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.


Texto completo:

PDF

Apontamentos

  • Não há apontamentos.


ISSN (online): 2447-5386