Um estudo aplicado de paralelismo para o problema do subgrafo planar de peso máximo
Nenhuma Miniatura disponível
Data
2018-04-27
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
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.
Descrição
Palavras-chave
Citação
COELHO, 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.