Uma proposta de solução aproximada para o problema do subgrafo planar de peso máximo - Coelho, Vinícius; Martins, Wellington; Foulds, Leslie; Dias, Elisângela; Castonguay, Diane; Longo, Humberto (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), 2016)
A proposta deste trabalho consiste em uma solução aproximada para o problema do subgrafo planar de peso máximo (WMPG Weighted Maximal Planar Graph). O algoritmo baseia-se na adição de vértices, aproveitando-se da construção de triangulações nas faces do grafo. A vantagem do uso deste algoritmo dá-se pelo fato que todo grafo gerado por ele é maximal planar, descartando a necessidade de um teste de planaridade. Apresentamos um algoritmo sequencial e um paralelo para o problema WMPG e suas respectivas implementações. Os resultados obtidos com a versão paralela executando em uma arquitetura manycore, com instâncias de até 85 vértices, apresentaram speedups de até 107 vezes em relação à solução sequencial.