Submitted 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) / Approved 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) / Made 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-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The 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. / O 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/8503 |
| Date | 27 April 2018 |
| Creators | Coelho, Vinícius de Sousa |
| Contributors | Martins, Wellington Santos, Martins, Wellington Santos, Foulds, Leslie Richard, Dias, Elisângela Silva, Drummond, Lúcia M. A. |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571 |
Page generated in 0.0112 seconds