skip to main content
Idioma:

Análise experimental de algoritmos de planaridade

Noma, Alexandre

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2003-05-09

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Análise experimental de algoritmos de planaridade
  • Autor: Noma, Alexandre
  • Orientador: Fernandes, Cristina Gomes
  • Assuntos: Algoritmos E Estruturas De Dados
  • Notas: Dissertação (Mestrado)
  • Descrição: O problema da planaridade consiste em: dado um grafo G, decidir se G é ou não é planar. A resposta deve vir acompanhada de uma justificativa. Se G é planar, então uma justificativa é uma representação de um desenho de G no plano sem cruzamento de arestas. Se G não é planar, então uma justificativa é uma subdivisão do 'K IND.3,3' ou do 'K IND. 5' em G. Existem vários algoritmos lineares para testar planaridade. Dois deles são bem conhecidos: o algoritmo proposto por Auslander e Parter [1], posteriormente corrigido por Goldstein [9] (APG), e o algoritmo proposto por Lempel, Even e Cederbaum [12] (LEC). Hopcroft e Tarjan [10] apresentaram em 1974 a primeira implementação linear do algoritmo de APG. Pouco depois, Booth e Lueker apresentaram uma implementação linear do algoritmo de LEC, introduzindo uma nova estrutura de dados chamada PQ-árvore. Recentemente, Shih e Hsu [15] e Boyer e Myrvold [3] publicaram duas implementações lineares do algoritmo de LEC que evitam o uso da PQ-árvore. Este trabalho apresenta uma descrição do algoritmo de LEC e uma descrição da implementação de Shih e Hsu, bem como um estudo comparativo desta implementação com as implementações de Hopcroft e Tarjan, Booth e Lueker e de Boyer e Myrvold
  • DOI: 10.11606/D.45.2003.tde-20210729-133142
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2003-05-09
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.