Um estudo aplicado de paralelismo para o problema do subgrafo planar de peso máximo
Saved in:
| Hovedforfatter: | |
|---|---|
| Publication Date: | 2018 |
| Format: | Master thesis |
| Sprog: | por |
| Source: | Repositório Institucional da UFG |
| Download full: | http://repositorio.bc.ufg.br/tede/handle/tede/8503 |
Summary: | 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. |