Biblioteca Digital da UEM: Sistema Nou-Rau
Pgina Principal  Portugus   English  Español   Aumentar Texto  Texto Normal  Diminuir Texto
  Principal | Apresentao | Objetivos | Instrues Autores | Estatsticas | Outras Bibliotecas Digitais
  Sistema Integrado de Bibliotecas - SIB / UEM
Entrar | acessos | verso 1.1  
ndice
Pgina principal
Documentos
Novidades
Usurios

Aes
Consultar
Procurar
Exibir estatsticas

Procurar por:
Procura avanada

Dvidas e sugestes


Consultar: Programa de Ps-Graduao em Cincia da Computao

Incio > Dissertaes e Teses > Cincias Exatas e da Terra > Cincia da Computao > Programa de Ps-Graduao em Cincia da Computao

Ttulo [PT]: Planarizao de grafos por remoo de vrtices.
Ttulo [EN]: Graph planarization by vertex deletion.
Autor(es): Rodrigo Lankaites Pinheiro
Palavras-chave [PT]:

Planarizao de grafos. Grafos. Algoritmos em grafos. st-numerao. Algoritmo gentico. rvore-PQ.
Palavras-chave [EN]:
Graph planarization. Graph algorithms. st-numbering. Genetic algorithm. PQ-tree
rea de concentrao: Cincia da Computao
Titulao: Mestre em Cincia da Computao
Banca:
Ademir Aparecido Constantino [Orientador] - DIN/UEM
Airton Marco Polidorio - DIN/UEM
Candido Ferreira Xavier de Mendona Neto - EACH/USP
Resumo:
Resumo: Neste trabalho so propostos dois algoritmos que utilizam a operao de remoo de vrtices para se obter um subgrafo planar. O nmero de remoo de vrtices de um grafo G o menor inteiro K_> 0 tal que exista um subgrafo planar induzido de G obtido pela remoo de K vrtices de G. Considerando que o problema de deciso associado NP-completo, este trabalho prope o algoritmo heurstico VD-PLANARIZE de complexidade 0(m + n) para a planarizao de grafos utilizando a estrutura de dados rvores-PQ, a operao de remoo de vrtices e st-numerao. Outra proposta apresentada a do algoritmo gentico GAVD-PLANARIZE que busca melhorar as solues do VD-PLANARIZE. Este trabalho apresenta detalhes da implementao dos dois algoritmos bem como os resultados que comprovam a complexidade terica 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.
Data da defesa: 28/08/2009
Cdigo: vtls000175004
Informaes adicionais:
Idioma: Portugus
Data de Publicao: 2009
Local de Publicao: Maring
Orientador: Prof. Dr. Ademir Aparecido Constantino
Instituio: Universidade Estadual de Maring. Departamento de Informtica
Nvel: Dissertao (mestrado em Cincia da Computao) /
UEM. Programa de Ps-Graduao em Cincia da Computao

Responsavel: salete
Categoria: Aplicao
Formato: Documento PDF
Arquivo: Pinheiro-Rodrigo-2009-ME-DIN.pdf
Tamanho: 5871 Kb (6011740 bytes)
Criado: 03-11-2009 14:49
Atualizado: 04-11-2009 07:59
Visitas: 1001
Downloads: 18

[Visualizar]  [Download]

Todo material disponvel neste sistema de propriedade e responsabilidade de seus autores.