Análise experimental de algoritmos de planaridade (2003)
- Authors:
- Autor USP: NOMA, ALEXANDRE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: ALGORITMOS E ESTRUTURAS DE DADOS
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 09.05.2003
-
ABNT
NOMA, Alexandre. Análise experimental de algoritmos de planaridade. 2003. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2003. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-133142/. Acesso em: 29 dez. 2025. -
APA
Noma, A. (2003). Análise experimental de algoritmos de planaridade (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-133142/ -
NLM
Noma A. Análise experimental de algoritmos de planaridade [Internet]. 2003 ;[citado 2025 dez. 29 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-133142/ -
Vancouver
Noma A. Análise experimental de algoritmos de planaridade [Internet]. 2003 ;[citado 2025 dez. 29 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-133142/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
