Análise experimental de algoritmos para teste de planaridade

• Processo: 00/03969-2
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de julho de 2000
• Data de Término da vigência: 30 de junho de 2002
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cristina Gomes Fernandes
• Beneficiário: Alexandre Noma
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 96/04505-2 - Aspectos estruturais e algorítmicos de objetos combinatórios, AP.TEM
• Assunto(s): Algoritmos Grafos
• Palavra(s)-Chave do Pesquisador: Algoritmos | Grafos | Grafos Planares | Implementacao | Teste De Planaridade

Resumo

Existem situações práticas onde é necessário determinarmos se um dado grafo pode ser desenhado no plano de tal forma que suas arestas só se intersectem nos pontos extremos. Por exemplo, em projetos de circuitos VLSI, existe o interesse em decidir se um grafo que representa um circuito elétrico pode ser desenhado no plano desta forma. Nosso objetivo com este projeto é realizar uma análise experimental de algoritmos e estruturas de dados existentes que testam se um dado grafo pode ou não ser desenhado no plano e, se for o caso, encontrar um tal desenho. Para fazermos este estudo implementaremos algoritmos e tentaremos compreender como eles se comportam na prática, e se existe algum algoritmo entre estes que pode ser chamado, em algum sentido, de 'o melhor'. Gostaríamos se possível, de ao final da dissertação podermos fazer afirmações do tipo: o algoritmo A é melhor que o algoritmo B no que diz respeito ao critério X (por exemplo, número de operações, acessos a memória, tempo de execução em uma máquina específica, ...). (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

NOMA, Alexandre. Análise experimental de algoritmos de planaridade. 2003. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.