Pantheon Repositório Institucional da UFRJ
Coleta, preserva e divulga a produção acadêmica digital em todas as áreas do conhecimento.
São os ativos do repositório, além de teses e dissertações da UFRJ, artigos científicos, livros eletrônicos, capítulos de livros e trabalhos apresentados em eventos por professores, pesquisadores, funcionários administrativos e alunos de mestrado e doutorado.
Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/11422/11192| Tipo: | Trabalho de conclusão de graduação |
| Título: | Uma implementação do algoritmo de reconhecimento de grafos de disco unitário |
| Autor(es)/Inventor(es): | Ney, Rodrigo Toscano |
| Orientador: | Sá, Vinícius Gusmão Pereira de |
| Resumo: | O trabalho descreve um algoritmo para solucionar o problema de reconhecimento de um grafo de disco unitário. Um grafo de disco unitário (GDU) é representado por discos de diâmetro unitário no plano euclidiano em que, para nós vizinhos, os discos se sobrepõem, ou seja, os nós são retratados por discos e as arestas são definidas pela distância entre o centro desses discos. No caso de nós vizinhos a distância euclidiana é inferior ou igual a uma unidade de medida. O reconhecimento deste conjunto de grafos é conhecidamente um problema NP-Difícil. Um algoritmo que se utiliza do paradigma de computação concorrente para solução computacional deste problema é aqui proposto. A solução se baseia em discretizar o plano, aproximando qualquer posição de nós para a coordenada encontrada no canto inferior esquerdo de cada célula de uma malha. Os nós de um grafo são então exaustivamente posicionados nesta malha, respeitando as regras de vizinhança estabelecidas pela distância entre os nós. São testados diferentes tamanhos de malhas aonde o algoritmo tem boa chance de concluir se um grafo é GDU. |
| Palavras-chave: | Grafos Geometria computacional Discretização |
| Assunto CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO |
| Unidade produtora: | Instituto de Computação |
| Editora: | Universidade Federal do Rio de Janeiro |
| Data de publicação: | 5-Ago-2019 |
| País de publicação: | Brasil |
| Idioma da publicação: | por |
| Tipo de acesso: | Acesso Aberto |
| Aparece nas coleções: | Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| RTNey.pdf | 425.1 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.