Complexity of PQR tree construction

Orientador: João MeidanisDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: 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 descritosAbstract: PQR trees are data structures used to solve the consecutive ones problem and other related problems. Applications include interval or planar graph recognition, and problems involving DNA molecules. This dissertation aims at consolidating existing and new knowledge about PQR trees and, primarily, their online construction, thus providing a theoretical basis for the use of this structure in applications. This work presents a detailed description of the online PQR tree construction algorithm's design, starting with a naive implementation of the suggested operations and refining them successively, culminating with an almost-linear time complexity. In this project, we dealt with an obstacle that arises with the use of union-find structures and that has never been addressed before. The proof presented here for the time complexity is also novel and clearer. Furthermore, the project is accompanied by a Java implementation of all the algorithms describedMestradoCiência da ComputaçãoMestre em Ciência da Computaçã