Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275945
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Propriedade dos uns consecutivos e arvores PQR
Author: Telles, Guilherme Pimentel, 1972-
Advisor: Meidanis, João, 1960-
Abstract: 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
Subject: Estruturas de dados (Computação)
Algoritmos
Language: Português
Editor: [s.n.]
Date Issue: 1997
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Telles_GuilhermePimentel_M.pdf2.8 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.