Please use this identifier to cite or link to this item:
http://hdl.handle.net/11612/5366| Authors: | Silva, Kedson Alves |
| metadata.dc.contributor.advisor: | Santos, Tanilson Dias dos |
| Title: | Um estudo sobre grafos B2-EPG e B2-EPG-Helly |
| Keywords: | Complexidade;Grafos;Propriedade Helly;Representação EPG;Complexity;Graphs;Helly Property;EPG representation |
| Issue Date: | 5-May-2023 |
| Publisher: | Universidade Federal do Tocantins |
| Citation: | 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 |
| metadata.dc.description.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 |
| Appears in Collections: | Ciência da Computação |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Kedson Alves Silva - Monografia.pdf | 966.64 kB | Adobe PDF |  View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.