2018-05-222018-04-27COELHO, 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.http://repositorio.bc.ufg.br/tede/handle/tede/8503The 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.application/pdfAcesso AbertoPlanaridadeMWPSPParalelismoCUDAPlanarityParallelismCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAODissertação