Propriedade dos uns consecutivos e arvores PQR

Autor: Telles, Guilherme Pimentel, 1972
Přispěvatelé: Meidanis, João, 1960, Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação, UNIVERSIDADE ESTADUAL DE CAMPINAS
Rok vydání: 2021
Předmět:
Zdroj: Biblioteca Digital de Teses e Dissertações da Universidade Estadual de Campinas (UNICAMP)
Universidade Estadual de Campinas (UNICAMP)
instacron:UNICAMP
DOI: 10.47749/t/unicamp.1997.128505
Popis: Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Neste trabalho formalizamos as Árvores PQR de Meidanis e Munuera e seu relacionamento com a propriedade dos uns consecutivos e com as Árvores PQ de Booth e Lueker. Mostramos que uma árvore PQR construída para uma coleção C de subconjuntos de um universo U é capaz de armazenar todas as permutações de U que verificam a propriedade dos uns consecutivos. Apresentamos dois algoritmos para construir as árvores PQR, um recursivo e outro não recursivo, e alguns problemas relativos à propriedade e às coleções de conjuntos que podem ser resolvidos através destas árvores. Analisamos, ainda, um conjunto de aplicações das Árvores PQ e consideramos a possibilidade de empregar as árvores PQR Abstract: In the present work we formalize Meidanis and Munuera's PQR trees and their relationship with the Consecutive Ones Property and with Booth and Lueker's PQ trees. We show that a PQR tree built for a colIection C of subsets of a ground set U is able to store alI permutations of U that verify the consecutive ones property. We introduce two algorithms that build the PQR trees, a recursive and a non recursive one, and some problems related to the consecutive ones property and to colIections of sets that can be solved using them. We analyze some applications of the PQ trees and inspect the useness of the PQR trees Mestrado Mestre em Ciência da Computação
Databáze: OpenAIRE
Externí odkaz: