Complexity of PQR tree construction

Author(s)

João Paulo Pereira Zanetti

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2012-02-27

Examining board members

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

• Advisor: João Meidanis

Abstract

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 described (AU)

• FAPESP's process: 10/04071-1 - Complexity of PQR Tree Construction
• Grantee: João Paulo Pereira Zanetti
• Support Opportunities: Scholarships in Brazil - Master