Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11612/5366
Autor(a): Silva, Kedson Alves
Orientador: Santos, Tanilson Dias dos
Título: Um estudo sobre grafos B2-EPG e B2-EPG-Helly
Palavras-chave: Complexidade;Grafos;Propriedade Helly;Representação EPG;Complexity;Graphs;Helly Property;EPG representation
Data do documento: 5-Mai-2023
Editor: Universidade Federal do Tocantins
Citação: SILVA, Kedson Alves. Um estudo sobre grafos B2-EPG e B2-EPG-Helly. 2022. 62 f. TCC (Graduação) - Curso de Ciência da Computação, Universidade Federal do Tocantins, Palmas, 2022
Resumo: A palavra EPG é um acrônimo para Edge-intersection Paths on a Grid, isto é, representa exatamente a classe de grafos de aresta-interseção de caminhos sobre uma grade. Neste trabalho de conclusão de curso iremos explorar principalmente uma subclasse de grafos EPG, conhecida como B2-EPG-Helly (mais especificamente a sua complexidade de reconhecimento). Contudo, também investigamos representações de grafos que não são B1-EPG, mas ainda não foram associadas a alguma classe Bk- EPG, além de estudar outras propriedades de caminhos em B2-EPG e B2-EPG com a propriedade Helly. Essa pesquisa contém resultados iniciais inéditos sobre a exploração da classe B2- EPG, além de propor tópicos interessantes para trabalhos futuros
Abstract: The word EPG is an acronym for Edge-Intersecting Paths on a Grid, that is, it exactly represents the class of edge-intersecion graphs of paths on a grid. In this writing, we started exploring the EPG graph subclass, well known as B2-EPG-Helly (more specifically its recognition complexity). However, we have also investigated graph representations that are not B1-EPG, but have not yet been associated with any Bk-EPG class, and also study other path properties in B2-EPG and B2-EPG with the Helly property. This research contains initial unpublished results about an exploration of the class B2- EPG, in addition to proposing interesting topics for future work
URI: http://hdl.handle.net/11612/5366
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Kedson Alves Silva - Monografia.pdf966.64 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.