Reconhecimento de grafos IIC-comparabilidade

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorGuedes, Andre Luiz Pires, 1966--
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática-
Autor(es): dc.creatorGlir, Lucas Ferreira-
Data de aceite: dc.date.accessioned2025-09-01T13:38:29Z-
Data de disponibilização: dc.date.available2025-09-01T13:38:29Z-
Data de envio: dc.date.issued2023-05-02-
Data de envio: dc.date.issued2023-05-02-
Data de envio: dc.date.issued2021-
Fonte completa do material: dc.identifierhttps://hdl.handle.net/1884/82293-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/82293-
Descrição: dc.descriptionOrientador: André Luiz Pires Guedes.-
Descrição: dc.descriptionDissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa : Curitiba, 25/10/2022-
Descrição: dc.descriptionInclui referências: p. 28-
Descrição: dc.descriptionÁrea de concentração: Ciência da Computação-
Descrição: dc.descriptionResumo: As relações binárias que são reflexivas, antissimétricas e transitivas são o que chamamos de ordem parcial. Podemos representar ordens parciais através de grafos de comparabilidade. Um grafo de comparabilidade é fechado sob interseção de intervalos (IIC) (Groshaus e Guedes, 2021) se, para cada vértice do grafo, o intervalo de predecessores e o intervalo de sucessores são fechados sob interseção. Em Groshaus e Guedes (2021), viu-se que é necessário que todo C4 tenha um vértice central universal, formando uma 4-roda, para que algum grafo de comparabilidade seja IIC. Nesta dissertação apresentamos mais uma propriedade dessa classe que generaliza esse resultado para C4s consecutivos e formulamos um algoritmo de reconhecimento da classe em programação linear inteira. Apesar disso, ainda não sabemos se o reconhecimento desta classe pode ser feito em tempo polinomial ou se é um problema NP-completo.-
Descrição: dc.descriptionAbstract: Binary relations that are reflexive, antisymmetric and transitive are what we call partial orders. We can represent partial orders through comparability graphs. A comparability graph is interval intersection closed (IIC) (Groshaus e Guedes, 2021) if, for any vertice of the graph, the predecessors interval and successors interval are closed under intersection. In Groshaus e Guedes (2021), its been shown that every C4 must have a central universal vertice, forming a 4-wheel, for a comparability graph to be IIC. In this dissertation we present a new property of the class that generalizes this result to consecutive C4s and we formulate a recognition algorithm for the class using integer linear programming. Nevertheless, its still an open problem if the recognition of this class can be done in polinomial time or if its a NP-complete problem.-
Formato: dc.format1 recurso online : PDF.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Palavras-chave: dc.subjectAlgorítmos de computador-
Palavras-chave: dc.subjectMetodo de decomposição-
Palavras-chave: dc.subjectCiência da computação-
Título: dc.titleReconhecimento de grafos IIC-comparabilidade-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.