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 | Tamanho | Formato | |
|---|---|---|---|---|
| Kedson Alves Silva - Monografia.pdf | 966.64 kB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.