Um estudo aplicado de paralelismo para o problema do subgrafo planar de peso máximo

Página do item simplificado
dc.contributor.advisor1Martins, Wellington Santos
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/3041686206689904eng
dc.contributor.referee1Martins, Wellington Santos
dc.contributor.referee2Foulds, Leslie Richard
dc.contributor.referee3Dias, Elisângela Silva
dc.contributor.referee4Drummond, Lúcia M. A.
dc.creatorCoelho, Vinícius de Sousa
dc.creator.Latteshttp://lattes.cnpq.br/2949127746947483eng
dc.date.accessioned2018-05-22T12:14:46Z
dc.date.issued2018-04-27
dc.description.abstractThe Maximum Weight Planar Subgraph Problem (MWPSP) consists of identifying a planar subgraph of maximum weight of a given edge-weighted graph. This work proposes new heuristic solutions, mainly using Graphic Processing Units, based on local transformations on the graph topology, consisting of vertex and edge insertion/relocation moves. Sequential and parallel implementations were built and applied to various numerical instances with promising results. One of the approaches requires only 25 seconds of execution, being more than 200 times faster than its corresponding sequential version, for a 100-vertex instance. In terms of quality, the proposed solutions obtained better results than state of the art proposals.eng
dc.description.provenanceSubmitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-05-21T15:48:27Z No. of bitstreams: 2 Dissertação - Vinícius de Sousa Coelho - 2018.pdf: 1071318 bytes, checksum: fba98fd6feb916f0400af915d4d92a2b (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-05-22T12:14:46Z (GMT) No. of bitstreams: 2 Dissertação - Vinícius de Sousa Coelho - 2018.pdf: 1071318 bytes, checksum: fba98fd6feb916f0400af915d4d92a2b (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceMade available in DSpace on 2018-05-22T12:14:46Z (GMT). No. of bitstreams: 2 Dissertação - Vinícius de Sousa Coelho - 2018.pdf: 1071318 bytes, checksum: fba98fd6feb916f0400af915d4d92a2b (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-04-27eng
dc.description.resumoO problema do subgrafo planar de peso máximo (MWPSP) consiste em extrair um subgrafo planar maximal, a partir de um grafo completo com pesos atribuídos às arestas, cuja soma dos pesos das arestas seja máxima. Este trabalho propõe soluções heurísticas, construídas por meio de Unidades de Processamento Gráfico (GPUs), baseadas em transformações locais na topologia do grafo através da inserção/realocação de vértices e arestas. Implementações sequencias e paralelas foram propostas, apresentando resultados satisfatórios. Em uma das propostas, a versão paralela requer cerca de 25 segundos de execução em uma instância de 100 vértices, sendo cerca de 200 vezes mais rápida que a versão sequencial correspondente. Em termos de qualidade da solução, as propostas superaram os resultados obtidos por algoritmos no estado da arte.eng
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESeng
dc.formatapplication/pdf*
dc.identifier.citationCOELHO, V. S. Um estudo aplicado de paralelismo para o problema do subgrafo planar de peso máximo. 2018. 69 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2018.eng
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/8503
dc.languageporeng
dc.publisherUniversidade Federal de Goiáseng
dc.publisher.countryBrasileng
dc.publisher.departmentInstituto de Informática - INF (RG)eng
dc.publisher.initialsUFGeng
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)eng
dc.rightsAcesso Aberto
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectPlanaridadepor
dc.subjectMWPSPpor
dc.subjectParalelismopor
dc.subjectCUDApor
dc.subjectPlanarityeng
dc.subjectParallelismeng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOeng
dc.titleUm estudo aplicado de paralelismo para o problema do subgrafo planar de peso máximoeng
dc.title.alternativeAn applied study using parallelism for the maximum weight planar subgraph problemeng
dc.typeDissertaçãoeng

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Vinícius de Sousa Coelho - 2018.pdf
Tamanho:
1.02 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)