| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
16/08/2002 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
- Marcelo Henriques de Carvalho
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Edson Norberto Caceres
- José Coelho de Pina Junior
- Marcelo Henriques de Carvalho
|
| Resumo |
Este Trabalho Trata De Reconhecer A Classe Dos Grafos Planares, Ou Seja, Grafos Que Admitem Uma Representação No Plano Sem Cruzamento De Arestas. Algoritmos Com Complexidade De Tempo Linear Para O Reconhecimento De Grafos Planares São Conhecidos Desde A Década De 70. Dois Deles São Clássicos Mas Complexos. São Eles Os Algoritmos De Hopcroft E Tarjan, E De Booth E Lueker. Mais Recentemente, Shih E Hsu Encontraram Um Outro Algoritmo Eficiente, Que Vem Sendo Considerado Mais Simples Que Os Anteriores. Examinamos Estes Três Algoritmos Eficientes Quanto à Forma Como Caracterizam Planaridade E Proporcionam Complexidade Linear Aos Algoritmos. Procuramos Apresentar De Maneira Mais Clara Possível Os Dois Algoritmos Clássicos E Discutir A Simplicidade Aparente Do Algoritmo De Shih E Hsu. |
| Download |
|
|