Use este identificador para citar ou linkar para este item:
http://repositorio.uem.br:8080/jspui/handle/1/2545
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.advisor | Ademir Aparecido Constantino | pt_BR |
dc.contributor.author | Pinheiro, Rodrigo Lankaites | pt_BR |
dc.date.accessioned | 2018-04-10T20:12:23Z | - |
dc.date.available | 2018-04-10T20:12:23Z | - |
dc.date.issued | 2009 | pt_BR |
dc.identifier.uri | http://repositorio.uem.br:8080/jspui/handle/1/2545 | - |
dc.description.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. | en |
dc.language | por | pt_BR |
dc.publisher | Universidade Estadual de Maringá | pt_BR |
dc.rights | openAccess | pt_BR |
dc.subject | Planarização de grafos | pt_BR |
dc.subject | Grafos | pt_BR |
dc.subject | Algoritmos em grafos | pt_BR |
dc.subject | st-numeração | pt_BR |
dc.subject | Algoritmo genético | pt_BR |
dc.subject | Árvore-PQ. | pt_BR |
dc.subject | Graph planarization | en |
dc.subject | Graph algorithms | en |
dc.subject | st-numbering | en |
dc.subject | Genetic algorithm | en |
dc.subject | PQ-tree | en |
dc.title | Planarização de grafos por remoção de vértices. | pt_BR |
dc.title.alternative | Graph planarization by vertex deletion. | en |
dc.type | masterThesis | pt_BR |
dc.contributor.referee1 | Airton Marco Polidorio - DIN/UEM | |
dc.contributor.referee2 | Candido Ferreira Xavier de Mendonça Neto - EACH/USP | |
dc.description.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. | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.program | Programa de Pós-Graduação em Ciência da Computação | pt_BR |
dc.publisher.initials | UEM | pt_BR |
dc.subject.cnpq1 | Ciências Exatas e da Terra | pt_BR |
dc.publisher.local | Maringá | pt_BR |
dc.description.physical | 92 f | pt_BR |
dc.subject.cnpq2 | Ciência da Computação | pt_BR |
dc.publisher.center | Departamento de Informática | pt_BR |
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.