Complexidade de construção de árvores PQR

Autor(es)

João Paulo Pereira Zanetti

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2012-02-27

Membros da banca

João Meidanis; Carlos Eduardo Ferreira; Guilherme Pimentel Telles

• Orientador: João Meidanis

Resumo

As árvores PQR são estruturas de dados usadas para tratar o problema dos uns consecutivos e problemas relacionados. Aplicações incluem reconhecimento de grafos de intervalos, de grafos planares, e problemas envolvendo moléculas de DNA. A presente dissertação busca consolidar o conhecimento sobre árvores PQR e, principalmente, sua construção incremental, visando fornecer uma base teórica para o uso desta estrutura em aplicações. Este trabalho apresenta uma descrição detalhada do projeto do algoritmo para construção online de árvores PQR, partindo de uma implementação inocente das operações sugeridas e refinando sucessivamente o algoritmo até alcançar a complexidade de tempo quase-linear. Neste projeto, lidamos com um obstáculo que surge com a utilização de estruturas de union-find que não havia sido tratado anteriormente. A demonstração da complexidade de tempo do algoritmo apresentada aqui também é nova e mais clara. Além disso, o projeto é acompanhado de uma implementação em Java dos algoritmos descritos (AU)

• Processo FAPESP: 10/04071-1 - Complexidade de Construção de Árvores PQR
• Beneficiário: João Paulo Pereira Zanetti
• Modalidade de apoio: Bolsas no Brasil - Mestrado