Busca avançada
Ano de início
Entree

Análise experimental de algoritmos para teste de planaridade

Processo: 00/03969-2
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de julho de 2000
Vigência (Término): 30 de junho de 2002
Área do 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

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)