Premium
A GRASP for graph planarization
Author(s) -
Resende Mauricio G. C.,
Ribeiro Celso C.
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199705)29:3<173::aid-net5>3.0.co;2-e
Subject(s) - grasp , greedy randomized adaptive search procedure , metaheuristic , heuristics , computer science , mathematical optimization , chemical mechanical planarization , heuristic , graph , set (abstract data type) , theoretical computer science , artificial intelligence , mathematics , engineering , polishing , mechanical engineering , programming language
A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describea GRASP for the graph planarization problem, extending the heuristic of Goldschmidt and Takvorian [Networks 24 (1994) 69–73]. We reviewthe basic concepts of GRASP: construction and local search algorithms.The implementation of GRASP for graph planarization is described in detail. Computational experience on a large set of standard test problems is presented. On almost all test problems considered, the new heuristic either matches or finds a better solution than previously described graph planarization heuristics. In several cases, previously unknown optima solutions are found. © 1997 John Wiley & Sons, Inc. Networks 29: 173–189, 1997