Complexidade de Construção de Árvores PQR

• Processo: 10/04071-1
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2010
• Data de Término da vigência: 29 de fevereiro de 2012
• Á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): Análise de algoritmos
• Palavra(s)-Chave do Pesquisador: propriedade dos uns consecutivos | Análise de Algoritmos

Resumo

Este projeto tenciona investigar a complexidade computacional de se constuir árvores PQR, que são estruturas de dados importantes no problema de permutar as colunas de uma matrix binária para fazer com que as linhas fiquem com seus 1s consecutivos, com aplicações em planaridade, grafos de intervalos e problemas em biologia computacional. Serão investigados algoritmos online e offline de construção destas árvores.

Publicações acadêmicas

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

ZANETTI, João Paulo Pereira. Complexidade de construção de árvores PQR. 2012. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.