Caracterizações, reconhecimento e conjuntos independentes máximos de grafos de intervalo

Página do item simplificado
dc.contributor.advisor1Nascimento, Julliano Rosa
dc.contributor.referee1Nascimento, Julliano Rosa
dc.contributor.referee1Castonguay, Diane
dc.creatorSouza, Ana Carolyne Pereira de
dc.date.accessioned2025-06-06T11:15:39Z
dc.date.available2025-06-06T11:15:39Z
dc.date.issued2024-12-09
dc.description.abstractA graph G is an interval graph if its vertex set can be represented by an interval intersection model on the real line. This monograph presents a study of some properties of interval graphs, such as the absence of induced cycles with four or more vertices and asteroidal triples. Based on the presented properties, given an interval graph G, we develop a polynomial-time algorithm that uses the perfect elimination scheme, obtained through the lexicographic breadth-first search algorithm, to create an interval model for the interval graph G. Additionally, we present a polynomial-time algorithm for determining a maximum independent set in an interval graph G. We also provide a characterization of unit interval graphs as interval graphs free of K1,3.
dc.description.resumoUm grafo G é um grafo de intervalo se seu conjunto de vértices pode ser representado através de um modelo de interseção de intervalos na reta real. Esta monografia apresenta um estudo sobre algumas propriedades de grafos de intervalo, como a ausência de ciclos induzidos com quatro ou mais vértices e triplas asteroidais. Com base nas propriedades apresentadas, dado um grafo de intervalo G, desenvolvemos um algoritmo polinomial que usa o esquema de eliminação perfeita, obtido através do algoritmo de busca em largura lexicográfica, para criar um modelo de intervalo para um grafo de intervalo G. Além disso, mostramos um algoritmo polinomial para determinar um conjunto independente máximo em um grafo de intervalo G. Também apresentamos uma caracterização de grafos de intervalo unitário como sendo grafos de intervalo livres de K1,3.
dc.identifier.citationSOUZA, Ana Carolyne Pereira de. Caracterizações, reconhecimento e conjuntos independentes máximos de grafos de intervalo. 2024. 44 f. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Instituto de Informática, Universidade Federal de Goiás, Goiânia, 2024.
dc.identifier.urihttp://repositorio.bc.ufg.br//handle/ri/27712
dc.language.isopor
dc.publisherUniversidade Federal de Goiás
dc.publisher.countryBrasil
dc.publisher.courseCiência da Computação (RMG)
dc.publisher.departmentInstituto de Informática - INF (RMG)
dc.publisher.initialsUFG
dc.rightsAcesso Aberto
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectTeoria dos grafos
dc.subjectGrafos de intervalo
dc.subjectModelo de interseção
dc.subjectAlgoritmo
dc.subjectConjunto independente
dc.subjectGraph theory
dc.subjectInterval graphs
dc.subjectIntersection model
dc.subjectAlgorithm
dc.subjectIndependent set
dc.titleCaracterizações, reconhecimento e conjuntos independentes máximos de grafos de intervalo
dc.title.alternativeCharacterizations, recognition, and maximum independent sets of interval graphs
dc.typeTrabalho de conclusão de curso de graduação (TCCG)

Arquivos

Pacote Original

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
TCCG - Ciência da Computação - Ana Carolyne Pereira de Souza - 2024.pdf
Tamanho:
1.59 MB
Formato:
Adobe Portable Document Format
Baixar

Licença do Pacote

Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

INF - Trabalhos de Conclusão de Curso