A constructive parallel heuristic approach for the MWPSP - Silva, Rafael C.; Coelho, Vinicius; Martins, Wellington; Longo, Humberto; Foulds, Leslie (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD); 2023: Anais do XXIV Simpósio em Sistemas Computacionais de Alto DesempenhoDO - 10.5753/wscad.2023.235873, 2023)
Algorithms for the problem of identifying a maximum edge-weight planar subgraph of a given edge-weighted graph G are relevant in a wide variety of application areas. In this paper, we propose a new local search constructive heuristic for this NP-hard problem, along with a GPU-based algorithm designed to accelerate its computational process. The experimental findings demonstrated that considerable speedup is attainable while maintaining good-quality results.