BDBComp
Parceria:
SBC
Um Algoritmo Evolutivo para Planarização de Grafos por Remoção de Vértices

Rodrigo Lankaites PinheiroCandido F. X. de MendoncaAdemir Aparecido Constantino

Um grafo não planar só pode ser planarizado se o mesmo for modificado. Neste trabalho é apresentado um algoritmo que utiliza a remoção de vértice para obter um subgrafo planar. A remoção de vértice de um grafo G é o menor inteiro k ? 0 tal que exista um subgrafo planar induzido de G obtido pela remoção de k vértices de G. Considerando que o problema de decisão correspondente é NP-completo e que não existe algoritmo de aproximação para planarização de grafos por remoção de vértices, este trabalho propõe um algoritmo evolutivo que utiliza um algoritmo construtivo de planarização de grafos, o qual possui complexidade de tempo O(n+m), baseado na estrutura de dados de árvores-PQ e na operação de remoção de vértices. A eficiência do algoritmo é verificada por meio de alguns estudos de casos.

http://www.din.uem.br/sbpo/sbpo2012/pdf/arq0399.pdf

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD