Planarização de grafos por remoção de vértices.

Pinheiro, Rodrigo Lankaites

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

Mostrar registro simples do item Visualizar estatísticas

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.