REPOSITÓRIO INSTITUCIONAL DA UNIVERSIDADE ESTADUAL DE MARINGÁ (RI-UEM)
A missão do Repositório Institucional da Universidade Estadual de Maringá (RI-UEM) é reunir, preservar e permitir o acesso à memória institucional (científica, técnica, artística e administrativa) da Universidade Estadual de Maringá em formato digital.
Use este identificador para citar ou linkar para este item:
http://repositorio.uem.br:8080/jspui/handle/1/2545| Autor(es): | Pinheiro, Rodrigo Lankaites |
| Orientador: | Ademir Aparecido Constantino |
| Título: | Planarização de grafos por remoção de vértices. |
| Título(s) alternativo(s): | Graph planarization by vertex deletion. |
| Banca: | Airton Marco Polidorio - DIN/UEM |
| Banca: | Candido Ferreira Xavier de Mendonça Neto - EACH/USP |
| Palavras-chave: | Planarização de grafos;Grafos;Algoritmos em grafos;st-numeração;Algoritmo genético;Árvore-PQ.;Graph planarization;Graph algorithms;st-numbering;Genetic algorithm;PQ-tree |
| Data do documento: | 2009 |
| Editor: | Universidade Estadual de Maringá |
| Resumo: | Neste trabalho são propostos dois algoritmos que utilizam a operação de remoção de vértices para se obter um subgrafo planar. O número de remoção de vértices 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 associado é NP-completo, este trabalho propõe o algoritmo heurístico VD-PLANARIZE de complexidade 0(m + n) para a planarização de grafos utilizando a estrutura de dados árvores-PQ, a operação de remoção de vértices e st-numeração. Outra proposta apresentada é a do algoritmo genético GAVD-PLANARIZE que busca melhorar as soluções do VD-PLANARIZE. Este trabalho apresenta detalhes da implementação dos dois algoritmos bem como os resultados que comprovam a complexidade teórica do VD-PLANARIZE e os bons resultados obtidos pelo GAVDPLANARIZE. |
| Abstract: | This work proposes two algorithms that use the vertex deletion operation to obtain a planar subgraph. The vertex deletion number of a graph G is the lower integer K _> 0 such that there is an induced planar subgraph obtained by the removal of K vertexes from G. Considering that the associated decision problem is NP-complete, this work proposes the 0 (m + n) heuristic algorithm VD-PLANARIZE to planarize graphs using the PQ-tree data structure, the vertex deletion operation and st-numbering. Another proposal is the genetic algorithm GAVD-PLANARIZE that looks forward to improve the solutions obtained by the VD-PLANARIZE. This work presents details of the implementation of both algorithms as well as the results that aver the theoretical complexity of VD-PLANARIZE and show the good results obtained by the GAVD-PLANARIZE. |
| URI: | http://repositorio.uem.br:8080/jspui/handle/1/2545 |
| Aparece nas coleções: | 2.4 Dissertação - Ciências de Tecnologia (CTC) |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 000175004.pdf | 5,87 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.