Teoria e Aplicações de Árvores PQ e PQR

• Processo: 08/11510-1
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de março de 2009
• Data de Término da vigência: 31 de dezembro de 2009
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: João Meidanis
• Beneficiário: João Paulo Pereira Zanetti
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Biologia computacional Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: algoritmos em grafos | análise amortizada | propriedade dos uns consecutivos | Biologia Computacional

Resumo

As árvores PQ foram introduzidas por Booth e Lueker em 1976. Uma árvore PQ é uma estrutura de dados que representa permutações de um conjunto de elementos em que certos subconjuntos ocorrem consecutivamente. Aplicações incluem reconhecimento de grafos de intervalos, de grafos planares, e problemas envolvendo moléculas de DNA.Apesar de sua grande popularidade me trabalhos teóricos, as árvores PQ são de difícil implementação. Neste trabalho, pretendemos dar continuidade ao desenvolvimento de uma estrutura mais geral, a árvore PQR, introduzida por Meidanis, Porto e Telles (1998), que tem boas possibilidades de se tornar uma alternativa mais fácil de implementar, além de dar mais informações sobre o problema.