Uma implementação do algoritmo de reconhecimento de grafos de disco unitário

Ney, Rodrigo Toscano

Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/11192

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Sá, Vinícius Gusmão Pereira de	-
dc.contributor.author	Ney, Rodrigo Toscano	-
dc.date.accessioned	2020-01-30T18:16:19Z	-
dc.date.available	2023-12-21T03:06:44Z	-
dc.date.issued	2019-08-05	-
dc.identifier.uri	http://hdl.handle.net/11422/11192	-
dc.language	por	pt_BR
dc.publisher	Universidade Federal do Rio de Janeiro	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.subject	Grafos	pt_BR
dc.subject	Geometria computacional	pt_BR
dc.subject	Discretização	pt_BR
dc.title	Uma implementação do algoritmo de reconhecimento de grafos de disco unitário	pt_BR
dc.type	Trabalho de conclusão de graduação	pt_BR
dc.contributor.advisorLattes	http://lattes.cnpq.br/1507369025671110	pt_BR
dc.contributor.authorLattes	http://lattes.cnpq.br/6905374679510794	pt_BR
dc.contributor.referee1	Rossetto, Silvana	-
dc.contributor.referee1Lattes	http://lattes.cnpq.br/0054098292730720	pt_BR
dc.contributor.referee2	Dourado, Mitre Costa	-
dc.contributor.referee2Lattes	http://lattes.cnpq.br/0841425239502177	pt_BR
dc.description.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 deﬁnidas 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.	pt_BR
dc.publisher.country	Brasil	pt_BR
dc.publisher.department	Instituto de Computação	pt_BR
dc.publisher.initials	UFRJ	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO	pt_BR
dc.embargo.terms	aberto	pt_BR
Appears in Collections:	Ciência da Computação

Files in This Item:

File	Description	Size	Format
RTNey.pdf		425.1 kB	Adobe PDF	View/Open

Show simple item record Recommend this item View Statistics

Pantheon Institutional repository