Paper Info
Title
A greedy random adaptive search procedure for the weighted maximal planar graph problem
Abstract
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(n3) to O(n2). The GH heuristic with the data structure is then integrated with advanced moves neighbourhood to develop an efficient GRASP implementation. Further, we investigate the behaviour of GRASP parameters in relation to the problem's characteristics. Finally, the developed algorithms are compared with the best-known procedures in the literature on a set of 100 test instances of sizes varying from 20 to 100 nodes.
Year
DOI
Venue
2003
10.1016/j.cie.2003.09.005
Computers & Industrial Engineering
Keywords
Field
DocType
Combinatorial optimisation problem,Data structures,Facility layout,Graph theory,Heuristics,Weighted maximal planar graph,Greedy random adaptive search procedure,Meta-heuristics
Graph theory,Complete graph,Combinatorics,Mathematical optimization,Planarity testing,GRASP,Graph factorization,Induced subgraph isomorphism problem,Planar graph,Subgraph isomorphism problem,Mathematics
Journal
Volume
Issue
ISSN
45
4
0360-8352
Citations 
PageRank 
References 
8
0.59
7
Authors
3
Name
Order
Citations
PageRank
Ibrahim H. Osman181594.23
Baydaa Al-Ayoubi2392.36
Musbah Barake3291.37