查看文章

The weighted maximal planar graph (WMPG) problem seeks to find a subgraph from a given weighted complete graph such that the subgraph is planar—it can be embedded on the plane without any arcs intersecting. The subgraph is maximal—no additional arc can be added to the subgraph without destroying its planarity and it also has the maximal sum of arc weights. In this paper, the main objective is to develop, implement and empirically analyse a new greedy random adaptive search procedure (GRASP) to solve the WMPG problem. A dynamic strategy to update the restricted candidate list is proposed. An efficient data structure is developed for the Green&Al-Hakim (GH) construction heuristic. The data structure reduces the GH complexity from O(n³) to O(n²). The GH heuristic with the data structure is then integrated with advanced moves neighbourhood to develop an efficient GRASP implementation. Further …