A constructive and improving heuristic algorithm for the maximum weight planar subgraph problem

Este trabalho aborda o problema de se identificar um subgrafo planar, de peso máximo, de um dado grafo G ponderado nas arestas, o qual é importante na modelagem e resolução de problemas das mais diversas áreas. É proposto um novo algoritmo heurístico de busca local, baseado em métodos previamente existentes de construção de soluções e de melhoria das mesmas, para este problema pertencente à classe NP-difícil de problemas de otimização. Quando avaliado com instâncias numéricas geradas sinteticamente, os resultados obtidos com o algoritmo proposto superaram os melhores até então disponíveis, obtidos com a combinação de outros dois métodos heurísticos anteriormente propostos para o problema.